【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

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXSIZE=10000020;
  5. int bufpos;
  6. char buf[MAXSIZE];
  7. #define NEG 0
  8. void init(){
  9.     #ifdef LOCAL
  10.         freopen("5139.txt","r",stdin);
  11.     #endif
  12.     buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  13.     bufpos=0;
  14. }
  15. #if NEG
  16. int readint(){
  17.     bool isneg;
  18.     int val=0;
  19.     for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  20.     bufpos+=(isneg=buf[bufpos]=='-');
  21.     for(;isdigit(buf[bufpos]);bufpos++)
  22.         val=val*10+buf[bufpos]-'0';
  23.     return isneg?-val:val;
  24. }
  25. #else
  26. int readint(){
  27.     int val=0;
  28.     for(;!isdigit(buf[bufpos]);bufpos++);
  29.     for(;isdigit(buf[bufpos]);bufpos++)
  30.         val=val*10+buf[bufpos]-'0';
  31.     return val;
  32. }
  33. #endif
  34. char readchar(){
  35.     for(;isspace(buf[bufpos]);bufpos++);
  36.     return buf[bufpos++];
  37. }
  38. int readstr(char* s){
  39.     int cur=0;
  40.     for(;isspace(buf[bufpos]);bufpos++);
  41.     for(;!isspace(buf[bufpos]);bufpos++)
  42.         s[cur++]=buf[bufpos];
  43.     s[cur]='\0';
  44.     return cur;
  45. }
  46. int n;
  47. int a[100003],cnt[100003];
  48. bool check(int x){
  49.     for(int i=0;i<=n;i++)
  50.         cnt[i]=0;
  51.     for(int i=1;i<x;i++)
  52.         cnt[a[i]]++;
  53.     int sum=0;
  54.     for(int i=0;i<=n;i++){
  55.         if (cnt[i] && sum+n-x<i)
  56.             return false;
  57.         sum+=cnt[i];
  58.     }
  59.     return true;
  60. }
  61. int main(){
  62.     init();
  63.     n=readint();
  64.     for(int i=1;i<=n;i++)
  65.         a[i]=readint();
  66.     int l=1,r=n;
  67.     while(l<r){
  68.         int mid=(l+r+1)/2;
  69.         if (check(mid))
  70.             l=mid;
  71.         else r=mid-1;
  72.     }
  73.     printf("%d",n-l);
  74. }

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

隐藏