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

LizaZay LizaZay    3   01.10.2019 21:50    0

Ответы
Erantpay22 Erantpay22  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;

}

ПОКАЗАТЬ ОТВЕТЫ
Другие вопросы по теме Информатика