P7584

Fat_Fish · 2021-05-04 21:20:24 · 题解

对于这样一个数列，我们可以先sort排序一遍，求出最小的第一名b_n+1,如果B_i+n>B_n+1,答案ans++即可

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int a[maxn];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;++i){
        if(i==n){
            ++ans;
            break;
        }
        if(a[i]+n>=a[n]+1){
            ++ans;
        }
    }
    cout<<ans<<'\n';
    return 0;
}

欢乐的爆零了。原来是因为如果出现有重复数据的情况下，B_n+1不一定是最大值,只需循环一遍求出最大值即可，注意:使第一名的人尽可能多，就要让最大值尽可能小。即a_i+n-i+1为最优。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int a[maxn];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);//读入优化，速度媲美scanf
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    sort(a+1,a+1+n);//从小到大一遍排序
    int mx=INT_MIN/3;//初始化一个很小的数，/3防溢出（好习惯，在此无用）
    for(int i=1;i<=n;++i){
        mx=max(mx,a[i]+n-i+1);//尽可能使最大值最小
    }
    for(int i=1;i<=n;++i){
        if(a[i]+n>=mx){
            ++ans;//超过最大值，累加
        }
    }
    cout<<ans<<'\n';//完美输出！
    return 0;
}