Решение задачи Dreamoon и сбор мест с Codeforces

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

Dreamoon — большой фанат соревнований на Codeforces!

Однажды, он сказал, что соберет все места от 1 до 54 после двух следующих рейтинговых контестов. Это удивительно!

Вдохновившись его высказыванием, вы придумали следующую задачу:

Есть человек, который принял участие в n раундах на Codeforces. Его место на первом раунде — a1, его место на втором раунде — a2, ..., его место на n-м раунде — an.

Вам дано положительное целое число x.

Пожалуйста, найдите наибольшее такое v, что этот человек сможет собрать все места от 1 до v спустя x следующих рейтинговых контестов.

Другими словами, вам нужно найти наибольшее v, что возможно такое, что после x следующих контестов, для каждого 1≤i≤v, будет существовать контест, в котором он занял i-е место.

Например, если n=6, x=2 и a=[3,1,1,5,7,10], то ответ v=5, так как, если занятые места в двух следующих раундах будут 2 и 4, то будут собраны все места от 1 до 5, то есть можно получить v=5.

Код 

#include <bits/stdc++.h>

using namespace std;
void solve(){
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    vector<int> res(500);
    for(int i = 0; i < n; ++i)
        res[a[i] - 1] = 1;

    for(int i = 0; i < res.size() && x > 0; ++i)
        if(!res[i]){
            res[i] = 1;
            --x;
        }
    for(int i = 0; i < res.size(); ++i)
        if(!res[i]){
            cout  << i << endl;
            return;
        }
    cout << res.size() << endl;
}
int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; ++i){
       solve();
    }

    return 0;
}

         

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



Комментарии

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



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp