Question

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

Answer 1

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

#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;

}

Answer 2

Для решения данной задачи можно использовать жадный алгоритм, который будет распределять конфеты с учетом желаний детей, начиная с наибольшего запроса. Таким образом, мы постараемся удовлетворить наиболее требовательных детей сначала, чтобы минимизировать сумму детского "гнева".

Вот алгоритм:

1. Создайте массив или список, в котором каждый элемент будет представлять пару (индекс ребенка, количество желаемых конфет).

2. Отсортируйте этот массив по убыванию желаемого количества конфет.

3. Распределите конфеты согласно желаниям детей, начиная с самого большого запроса и двигаясь к меньшим.

   • Если количество конфет (М) больше или равно желаемому количеству конфет текущего ребенка, дайте ему все конфеты, которые он хотел.
   • Если количество конфет (М) меньше желаемого количества текущего ребенка, дайте ему всё, что осталось в мешке, и перейдите к следующему ребенку, уменьшив его запрос на оставшееся количество конфет в мешке.

4. Посчитайте сумму детского "гнева" по формуле "количество недостающих конфет * количество недостающих конфет" для каждого ребенка.

5. Повторяйте шаги 3-4, пока все конфеты не будут распределены.

Этот алгоритм обеспечит минимальную сумму детского "гнева", так как мы стараемся удовлетворить наиболее требовательных детей в первую очередь, и если возникают конфликты в распределении, мы пытаемся минимизировать "гнев" ребенка с наибольшим запросом, оставив его с наименьшим недовольством.