题解 P2777 【[AHOI2016初中组]自行车比赛】

pipiispig · 2019-01-15 22:34:53 · 题解

一道贪心题硬生生被我做成了二分答案QWQ(最近做二分答案做多了？QWQ)

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm> 
using namespace std;
struct node{
    int x,y;
};
int s[1000000],b[1000000];  
int n;
int cmp(int x,int y){
    return x>y;
}
int cherk(int m){//按理说二分答案的难点就在于cherk函数上，然而这个cherk函数我们可以写的很暴力（更简单的说）；
    int q=s[m]+n;
    for(int i=1;i<m;i++){
        if(q<s[i]+b[i])return 0;
    }
    return 1;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i];
    sort(s+1,s+n+1,cmp);
    for(int j=1;j<=n;j++){
        b[j]=j;
    }//一个简单的贪心——>使排名越高的可以加的分越少,这样才会使分约高的人最后一场比赛获得得分约少，使所求人得冠军的几率更大；
    int l=1,ans,r=n;
    while(l<=r){//愉快的二分答案~
        int mid=l+r>>1;
        if(cherk(mid)){
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }
    cout<<ans;
}```