Решение задачи Пазлы с Codeforces

Без пояснения   Просмотров: 155

Учебный год подходит к концу, и классной руководительнице Манане Тариеловне скоро придется прощаться с очередным классом. На прощанье учительница решила подарить каждому из своих n учеников «пазл» (согласно wikipedia, пазл — игра-головоломка, в которой требуется составить мозаику из множества фрагментов рисунка различной формы).

В магазине учительнице сказали, что у них есть m пазлов, но они возможно не все одинаковой сложности и размера. Конкретно, первый пазл состоял из f1 фрагментов, второй — из f2, и так далее.

Манана Тариеловна решила, что разница между количествами фрагментов в подаренных ею пазлах должна быть как можно меньше, иначе дети могут обидеться. Поэтому она хочет выбрать такие n пазлов, что если A — это количество фрагментов в самом большом, а B — количество фрагментов в самом маленьком из них, то A - B должно быть минимальным возможным. Помогите учительнице и найдите наименьшую возможную разницу A - B.

Код 

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m, best = INFINITY;
    cin >> n >> m;
    vector<int> a(m);
    for(int i = 0; i < m; ++i){
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    for(int i = 0; i <= a.size() - n; ++i){
        best = min(best, a[i + n - 1] - a[i]);
    }
//    10 12 10 7 5 22
//    5 7 10 10 12 22
    cout << best;
    return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES [email protected] Карта сайта