【BZOJ5139】【LOJ2337】【Usaco2017 Dec】Greedy Gift Takers

Author Avatar
q234rty 1月 11, 2018

二分答案+排序即可。

容易发现如果一个人拿到过礼物，那么在他前面的人一定也拿到过礼物，于是可以二分答案，考虑怎么判定。

考虑在他前面的人必须都插到他后面，不难发现一个人 x 能拿到礼物当且仅当

\forall i \in [1,x),\sum_{j=1}^{x-1}[c_j<c_i] \geq c_i+i-n

排序之后扫一遍即可。

使用基数排序，时间复杂度 O(n \log n)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("5139.txt","r",stdin);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
int n;
int a[100003],cnt[100003];
bool check(int x){
    for(int i=0;i<=n;i++)
        cnt[i]=0;
    for(int i=1;i<x;i++)
        cnt[a[i]]++;
    int sum=0;
    for(int i=0;i<=n;i++){
        if (cnt[i] && sum+n-x<i)
            return false;
        sum+=cnt[i];
    }
    return true;
}
int main(){
    init();
    n=readint();
    for(int i=1;i<=n;i++)
        a[i]=readint();
    int l=1,r=n;
    while(l<r){
        int mid=(l+r+1)/2;
        if (check(mid))
            l=mid;
        else r=mid-1;
    }
    printf("%d",n-l);
}

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2018/01/11/bzoj5139/

隐藏