|
|
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner a = new Scanner(System.in); int x = a.nextInt(); //String x1 = a.nextLine(); int y = 0; int z = 0; int [] array1 = new int[x]; for(int i=0;i<x;i++) { array1[i] = a.nextInt(); y+=array1[i];
if(i==1 && array1[i] < array1[i-1] ) { int tmp = array1[i]; array1[i] = array1[i-1]; array1[i-1] = tmp; } }
for(int i=array1.length-1;i>-1;i--) { z+=array1[i]*y; y-=array1[i]; z+=array1[i]*y; }
System.out.println(z); } } sort the array. maintain W, the total weight of the array. start from the smallest element and add A[i] * W to ANS. subtract A[i] from W. add A[i] * W again. There is a better solution with O(1) memory and O(n) time (without sorting). Edited by author 20.09.2020 21:51 Edited by author 20.09.2020 21:51 Do you mind sharing this solution? I solved it using sorting but cannot think of another solution. answer = (sum of array) ^ 2 You can get it by simple math. Do you mind sharing this solution? I solved it using sorting but cannot think of another solution. 1. If time limit exceeded, use a better sorting algorithm. In my case, insertion sort spent barely over a second, while merge sort spent only 0.6 of a second. 2. used long long. Also, before multiplying a long long and an int together, convert the int first. Sorting the input is a waste of time, quite frankly. Try some of your own inputs, the solution can be very simple & fast. Is there any algorithm to be applied except sorting? Если мы можем оставлять часть груза в городах(любое кол-во груза), то ответ будет 24(может и меньше). Ошибка в условии или некорректно сформулировано условие? Цитата из условия: "Грузовик Платона загружается один раз в столице." Следовательно, если мы оставим часть груза в каком-то городе, то назад его погрузить уже не сможем. Messages should be written in English reshke'` , если бы он хотел, чтобы наши иностранные дружбаны его поняли, то я думаю написал бы на английском. a2ch : There is nothing called foreign friends, please remember we are global citizen first. We all are programmers and that is our identity. Please keep smiling. --------------------------- Там нет ничего, что называется иностранными друзьями, пожалуйста, помните, мы в первую очередь гражданин мира. Мы все программисты, и это наша личность. Пожалуйста, продолжай улыбаться. Let we visit towns by distance ascending: 1, 2, 3 So total fine is : (6+5) + (5*2+3*2) + 3 = 11 + 16 + 3 = 30 Where am I wrong? My mistake: Total fine is : (6+5) + (5*2+3*2) + 3*3 = 11 + 16 + 9 = 36 Can anyone please explain the sample solution given in the problem Edited by author 24.06.2019 13:55 use 'long' instead of 'int' as accumulator |
|
|