本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-02 13:10:42

题目
本题考察内容： 排序， 贪心， 二分， 前缀。

40~60 分做法

首先我们先将初始成绩降序排序， 方便运行。
要使第 $i$ 位选手获得第一名， 那么就要让其获得 $n$ 分， 让第 $1$，$2$，$\dots$，$i-1$ 位选手获得 $1$，$2$，$\dots$，$i-1$ 分， 让第 $i+1$，$i+2$，$\dots$，$n$ 位选手获得 $i$，$i+1$，$\dots$，$n-1$ 分。
如果第 $i$ 位选手是第一名， 那么他就能当第一名； 否则他就不能当第一名。
上面就是我们的贪心思想。
时间复杂度为 $O(n^2)$， 无法通过 $n\le 3\times 10^5$ 的数据。

100 分做法一

我们发现， 在循环内我们做了许多无用的事情， 我们可以提前处理好一个前缀最值， 后面直接调用即可。
总体时间复杂度为 $O(n)$（撇开排序）， 可以通过。
代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define reg register\/\/一点常数优化
using namespace std;
const int N=3e5+5; 
int a[N],n,maxx,sum;
inl int read(){\/\/快读函数， 可以直接用 cin 代替
	reg int f=1,x=0;
	reg char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
inl void write(int x){\/\/快写， 可用 cout 代替
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>=10) write(x\/10);
	putchar(x%10^48);
	return;
}
signed main(){
    n=read();
    for(reg int i=1;i<=n;++i) a[i]=read();
    sort(a+1,a+1+n,greater<int>());\/\/降序排序
    for(reg int i=1;i<=n;++i) maxx=max(maxx,a[i]+i);\/\/前缀最值
    for(reg int i=1;i<=n;++i)
        if(a[i]+n>=maxx) sum++;\/\/一重循环查找
    write(sum);
    return 0;
}

100 分做法二

我们发现， 如果第 $i$ 位选手能获得第一名， 那么第 $i-1$，$i-2$，$\dots$，$1$ 位选手都可以获得第一名； 如果第 $i$ 位选手不能获得第一名， 那么第 $i+1$，$i+2$，$\dots$，$n$ 为选手也不能获得第一名。
可以发现， 它具有单调性！
这说明， 此题可以使用二分。
时间复杂度为 $O(n\log_2n)$。
代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define reg register
#define N 300005
#define INF 2147483647
using namespace std;
int n,a[N],b[N];
inl int read(){
    reg int f=1,x=0;
    reg char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f*x;
}
inl void write(int x){
    if(x<0) x=-x;
    if(x>=10) write(x\/10);
    putchar(x%10^48);
}
inl bool check(int x){
    reg int tot=n-1;
    for(reg int i=1;i<=n;++i,--tot)
        if(b[i]!=a[x]&&(b[i]+tot>a[x]+n||b[i]+tot==a[x]+n&&i<x)) return false;\/\/这个判断条件可能有点难理解
    return true;
}
inl int lower(){\/\/二分模板
    reg int l=1,r=n,mid=0,ans=0;
    while(l<=r){
        mid=l+r>>1;\/\/位运算
        if(check(mid)){
            ans=mid;
            l=mid+1;
        }else r=mid-1;
    }
    return ans;
}
signed main(){
    n=read();
    for(reg int i=1;i<=n;++i) a[i]=read();
    memcpy(b,a,sizeof(a));\/\/复制数组，一个降序排，一个升序排
    sort(a+1,a+n+1,greater<int>());
    sort(b+1,b+n+1);
    write(lower());\/\/查找到的答案即此题答案
    return 0;
}

100 分做法三

你可以发现， 这两种方法是可以组合在一起的！
这样的话， 查找的时间复杂度仅为 $O(\log_2n)$！
代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define reg register
#define N 300005
#define INF 2147483647
using namespace std;
int n,a[N],maxx;
inl int read(){
    reg int f=1,x=0;
    reg char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f*x;
}
inl void write(int x){
    if(x<0) x=-x;
    if(x>=10) write(x\/10);
    putchar(x%10^48);
}
int lower(){
    int l=1,r=n,mid=0,ans=0;
    while(l<=r){
        mid=l+r>>1;
        if(a[mid]+n>=maxx){
            ans=mid;
            l=mid+1;
        }else r=mid-1;
    }
    return ans;
}
signed main(){
    n=read();
    for(int i=1;i<=n;++i) a[i]=read();
    sort(a+1,a+n+1,greater<int>());
    for(int i=1;i<=n;++i) maxx=max(maxx,a[i]+i);\/\/两种方法组合在一起，不解释
    write(lower());
    return 0;
}