В
Все
М
Математика
О
ОБЖ
У
Українська мова
Д
Другие предметы
Х
Химия
М
Музыка
Н
Немецкий язык
Б
Беларуская мова
Э
Экономика
Ф
Физика
Б
Биология
О
Окружающий мир
Р
Русский язык
У
Українська література
Ф
Французский язык
П
Психология
А
Алгебра
О
Обществознание
М
МХК
В
Видео-ответы
Г
География
П
Право
Г
Геометрия
А
Английский язык
И
Информатика
Қ
Қазақ тiлi
Л
Литература
И
История
saididag
saididag
21.07.2022 13:05 •  Информатика

Дети в детском саду получили большой мешок с конфетами. их в мешке м штук. решено, что конфеты должны быть распределены среди n детей. каждый ребенок указал количество конфет, которое он хочет. если ребенку не достанется такого количество конфет, которое он хочет, он будет обижен. «гнев» будет равным квадрату количества желаемых, но не полученных конфет. например, если вася утверждает, что хочет 32 конфеты, но получает лишь 29, ему не хватает 3 конфет, поэтому его «гнев» будет равным 9. распределить конфеты так, чтобы сумма детского гнева была минимальной. напишите алгоритм.

Показать ответ
Ответ:
SOSplizz
SOSplizz
09.10.2020 10:26
Решил жадным алгоритмом

#include <bits/stdc++.h>

using namespace std;

int ans,n,a[10101],m,b[10101];

main () {

   cin >>n >>m;

   for (int i = 1; i <= n; i++)

    cin >>a[i];

   sort(a + 1, a + n + 1);

for (int i = 1; i <= n; i++)

     if (a[i] <= m) m-=a[i];

     else

     b[i] = pow(a[i] - m,2);  

for (int i = 1; i <= n; i++)

 if (b[i]) ans+=b[i];

cout <<ans;

}

0,0(0 оценок)
Популярные вопросы: Информатика
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота