19 апреля, 18:11

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

+3
Ответы (1)
  1. 19 апреля, 19:00
    0
    Решил жадным алгоритмом

    #include

    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 <
    }
Знаете ответ на вопрос?
Не уверены в ответе?
Правильный ответ на вопрос 👍 «Дети в детском саду получили большой мешок с конфетами. Их в мешке М штук. Решено, что конфеты должны быть распределены среди N детей. ...» по предмету 📗 Информатика. Развернутая система поиска нашего сайта обязательно приведёт вас к нужной информации. Как вариант - оцените ответы на похожие вопросы. Но если вдруг и это не помогло - задавайте свой вопрос знающим оппонентам, которые быстро дадут на него ответ!
Искать готовые ответы
Новые вопросы по информатике
Объём видеопамяти составляет 100 Кбайт. Графический режим работает в режиме 640 х200 пикселей. Какое максимальное кол-во цветов может содержать палитра?
Ответы (1)
Переведите число 202 из восьмеричной системы счисления в десятичную
Ответы (1)
Переведите величины из одних единиц измерения информации в другие: 1 4 Гбайта=? Кбайт 2 217 Мбайт=? Гбайт 3 13 Мбит=? бит 4 27 Гбит=? бит 5 228 бит=? Мбайт 6 227 Гбит=? Мбайт 7 231 Кбайт=? Мбит
Ответы (1)
Вводятся 3 числа, вывести на экран нечетные числа pascal
Ответы (1)
1. Посчитай, сколько бит информации содержит 19 байт 2. Посчитай, сколько байт информации содержат 2 кб 3. Посчитай, сколько байт информации содержит 144 бит
Ответы (2)
Мощность первого в алфавита составляет 2048 символов информационный вес символа на второго алфавита она 2 бита меньше чем информационный вес символа из первого алфавита определите мощность второго алфавита
Ответы (1)
Известно правило кодирования - после каждой гласной буквы ставится буква "и", после каждой согласной - "ц". Зашифруй слова: практикум, принтер, секрет, честь.
Ответы (1)
Представить целое десятичное число 171 во внутримашинном представлении размером два байта.
Ответы (1)
Для записи текста использовался 64-символьный алфавит. Какое колисество информации в байтах содержит 3 страницы текста, если на каждой странице расположено 40 строк по 60 символов в строке?
Ответы (1)
Дано трехзначное число X. Проверить, будет ли произведение его цифр четным числом
Ответы (1)