Дети в детском саду получили большой мешок с конфетами. Их в мешке М штук. Решено, что...

Question

Дети в детском саду получили большой мешок с конфетами. Их в мешке М штук. Решено, что конфеты должны быть распределены среди N детей. Каждый ребенок указал количество конфет, которое он хочет. Если ребенку не достанется такого количество конфет, которое он хочет, он будет обижен. «Гнев» будет равным квадрату количества желаемых, но не полученных конфет. Например, если Вася утверждает, что хочет 32 конфеты, но получает лишь 29, ему не хватает 3 конфет, поэтому его «гнев» будет равным 9. Помогите распределить конфеты так, чтобы сумма детского гнева была минимальной. Напишите алгоритм.

Comments

на каком языке

---

Обычно под алгоритмом все поголовно почему-то имеют в виду блок-схему.

---

Мило. Оптимизационная задачка. Можно решать, например, симплекс-методом. Но я сомневаюсь, что кто-то будет тут расписывать его алгоритм.

---

C++

---

алгоритм я имел ввиду написать что да как делать

---

У Вас типичная оптимизационная задача. Гyглите методы решения таких задач и выбирайте любой. Но думаю, оно Вам не по зубам. Не знаю, где Вы такого монстрика вытащили.

---

Не по зубам говорите

---

Ну не знаю, раз сюда поместили вопрос...

Answer 1

Решил жадным алгоритмом

#include

using namespace std;

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

main () {

   cin >>n >>m;

   for (int i = 1; i

   cin >>a[i];

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

for (int i = 1; i

     if (a[i]

     else

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

for (int i = 1; i

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

cout

}