Решение задачи Байдарочный поход с Acmp

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


Компания из N человек собирается пойти в байдарочный поход, i-ый человек характеризуется своей массой Mi кг. На лодочной базе имеется в наличии неограниченное количество одинаковых байдарок. Каждая байдарка может вмещать одного или двух людей. Байдарки имеют грузоподъемность D кг. Какое наименьшее количество байдарок придется арендовать компании, чтобы всем отправиться в поход?

Код

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int n,d,m, k = 0;
    cin >> n >> d;
    bool b = 1, t = 1;
    vector<int> a;
    for(int i = 0; i < n; ++i){
        cin >> m;
        a.push_back(m);
    }
    sort(a.begin(),a.end());
    while(b){
        t = true;
        for(int i = a.size() - 1; i > 0; --i)
            if(a[i] + a[0] <= d){
                a.erase(a.begin());
                --i;
                a.erase(a.begin() + i);
                ++k;
                t = false;
            }
        if(a.size() < 2 || t)
            b = false;
        }
    if(a.size())
        k+=a.size();
    cout << k;
    return 0;
}

         

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




Комментарии

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