Борщ, картошка и салат

@reactive123 · Регистрация: 20.10.2018

Author24 — интернет-сервис помощи студентам

Сегодня в пластунов праздник! Привезли вдвое больше продуктов на обед. Зеник вместе с Марией согласились помогать на кухне. Всего есть три разных блюда: борщ, картофель и салат.

В пласте в Зеника и Маши есть N друзей. i-й друг хочет съесть Ai грамм борща, Bi грамм картофеля и Ci грамм салата. Если друг Зеника и Маши хочет съесть X грамм определенной блюда, а ему в тарелку положили Y грамм, то степень недоверия к Зеника с Марией у этого друга вырастет на | X-Y | единиц. Зеник с Марией приказали накладывать всем одинаковые порции определенной блюда. То есть каждому вторую нужно наложить A грамм борща, B грамм картофеля и C грамм салата.

Помогите Зенику и Марии выбрать такие A, B и C, чтобы суммарная степень недоверия всех друзей был как можно меньше.

Входные данные: В первой строке записано целое число N - количество друзей Зеника и Маши. В следующих N строках записаны по три целых числа Ai, Bi, Ci - количество борща, картошки и салата, которую хочет получить i-й друг.

Выходные данные: Одно целое число - суммарная степень недоверия всех друзей к Зеника и Маши.

Ограничение: 2 ≤ N ≤ 100000 (105) 30% тестов: 0 ≤ Ai, Bi, Ci ≤ 444 70% тестов: 0 ≤ Ai, Bi, Ci ≤ 10000 (104)

Пример ввода:
2
10 50 100
70 10 50
Пример вывода: 150
Подсказка: Одним из оптимальных для Зеника и Маши вариантов выбора чисел A, B, C будет A = 40, B = 30, C = 75. Тогда степень недоверия друзей будет следующим: Друг 1: | 40-10 | + | 30-50 | + | 75-100 | = 30 + 20 + 25 = 75 Друг 2: | 40-70 | + | 30-10 | + | 75-50 | = 30 + 20 + 25 = 75 Суммарный степень недоверия = 75 + 75 = 150
Пробовал так:

Pascal

program name;
var
   a,b,c:array[1..1000000] of word;
   n,i:2..1000000000;
   sa,sb,sc,s,a1,b1,c1:real;
begin
     read(n);
     for i:=2 to n+1 do
         begin
              read(a[i],b[i],c[i]);
              sa:=sa+a[i];
              sb:=sb+b[i];
              sc:=sc+c[i];
         end;
     a1:=sa/n;
     b1:=sb/n;
     c1:=sc/n;
     for i:=2 to n+1 do s:=s+abs(a[i]-a1)+abs(b[i]-b1)+abs(c[i]-c1);
     writeln(s:0:0);
end.

Это на основе того, что оптимальным вариантом выбора чисел, является среднее арифметическое всех А, В и С.

Добавлено через 14 минут
Но программа не проходит на 6-ом тесте

@кот Бегемот · 20.10.2018, 14:05

Сообщение от reactive123

Но программа не проходит на 6-ом тесте

Это неверное решение. Вернее, неверная идея. Среднее арифметическое здесь совсем не причём. Разберём простой пример.
Пусть гостей будет пятеро. Введём данные (они взяты практически с потолка):
5
8 6 5
7 3 2
4 6 2
5 1 8
2500 3200 4700
Ваша программа выдаёт ответ 16617, а минимум, которого можно достичь= 10495
как говорится, почувствуйте разницу.

@кот Бегемот · 20.10.2018, 14:28

Принцип решения очень простой. Для каждого блюда надо выбрать не среднее арифметическое, а среднее по порядку. Например, для чисел 1,2,3,4,638 средним будет 3. Если же число гостей чётное, то подойдёт как среднее с недостатком, так и среднее с избытком, например, если числа 2 4 9 345 можно брать и 4, и 9.

@vlados124 · 20.10.2018, 16:18

Вы все не так поняли. Имеется ввиду, среднее арифметическое каждого блюда. Например: в примере из задачи, среднее арифметическое блюда А равно (10+70)/2=40; блюда В - (50+30)/2=30; блюда С - (100+50)/2=75. И сумма равняется разности по модулю порции, предоставленной каждому другу и среднему арифметическому данного блюда.

@кот Бегемот · 20.10.2018, 19:13

Вот же идиот, ему решение рассказывают, а он упирается
Я-то как раз всё прекрасно понял ( я уже решал эту задачу), а вот ты, похоже, не понял ни фига. Ну,я тупых учить не нанимался. Прощай

PS. А проведи эксперимент: для данных чисел примера вместо среднего возьми ЛЮБОЕ число от начального до конечного (включая границы) и посчитай вручную. Результат тебя удивит.

@кот Бегемот Платежеспособный зверь 8924 / 4352 / 1642 Регистрация: 28.10.2009 Сообщений: 11,567
	20.10.2018, 14:05	2
	Сообщение от reactive123 Но программа не проходит на 6-ом тесте Это неверное решение. Вернее, неверная идея. Среднее арифметическое здесь совсем не причём. Разберём простой пример. Пусть гостей будет пятеро. Введём данные (они взяты практически с потолка): 5 8 6 5 7 3 2 4 6 2 5 1 8 2500 3200 4700 Ваша программа выдаёт ответ 16617, а минимум, которого можно достичь= 10495 как говорится, почувствуйте разницу. 0

@кот Бегемот Платежеспособный зверь 8924 / 4352 / 1642 Регистрация: 28.10.2009 Сообщений: 11,567
	20.10.2018, 14:28	3
	Принцип решения очень простой. Для каждого блюда надо выбрать не среднее арифметическое, а среднее по порядку. Например, для чисел 1,2,3,4,638 средним будет 3. Если же число гостей чётное, то подойдёт как среднее с недостатком, так и среднее с избытком, например, если числа 2 4 9 345 можно брать и 4, и 9. 0

@vlados124 1 / 1 / 0 Регистрация: 13.09.2018 Сообщений: 126
	20.10.2018, 16:18	4
	Вы все не так поняли. Имеется ввиду, среднее арифметическое каждого блюда. Например: в примере из задачи, среднее арифметическое блюда А равно (10+70)/2=40; блюда В - (50+30)/2=30; блюда С - (100+50)/2=75. И сумма равняется разности по модулю порции, предоставленной каждому другу и среднему арифметическому данного блюда. 0

@кот Бегемот Платежеспособный зверь 8924 / 4352 / 1642 Регистрация: 28.10.2009 Сообщений: 11,567
	20.10.2018, 19:13	5
	Вот же идиот, ему решение рассказывают, а он упирается Я-то как раз всё прекрасно понял ( я уже решал эту задачу), а вот ты, похоже, не понял ни фига. Ну,я тупых учить не нанимался. Прощай PS. А проведи эксперимент: для данных чисел примера вместо среднего возьми ЛЮБОЕ число от начального до конечного (включая границы) и посчитай вручную. Результат тебя удивит. 0

Опции темы