首先这道题的数据量1e5那么时间复杂度要保持在O(nlogn)内。
先判断单调性,若k头牛拿不到礼物,那么k-1头牛也拿不到礼物,所有这题可以用二分法来做(11110000)。
二分部分省略,我们直接来分析check部分(如下)。
bool check(int k){ for (int i=1;i<=n-k+1;i++) b[i]=a[i]; sort(b+1,b+n-k+1); int cnt=k-1; for (int i=1;i<=n-k;i++){ if (b[i]>cnt) return true; cnt++; } return false; }
我们判断k头牛拿不到礼物,只需要判断倒数第k头(即n-k+1头)牛拿不拿的到礼物,设这头牛为牛now。
牛now不能拿到礼物,说明它永远也挤不到第一的位置。
那么我们反向思考如果牛now能挤到第一的位置则返回false。
此时牛now及前面所有的牛都会到达第一并重新归队,所以在我们的假设中每头牛不论顺序如何都会到达牛now后方。接下来我们用贪心,优先让新位置靠后的牛先入队,尽量把牛now往前挤。
每有一头牛到达牛now后方那么让牛now位置保持不动的ci对应最小值cnt++;而如果此时ci>cnt,那么牛now就不可能再前进到达第一位了,因为排序之后的牛的新位置只可能在更前面。此时返回true。
主要代码:
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N],n,b[N]; bool check(int k){ for (int i=1;i<=n-k+1;i++) b[i]=a[i]; sort(b+1,b+n-k+1); int cnt=k-1; for (int i=1;i<=n-k;i++){ if (b[i]>cnt) return true; cnt++; } return false; } int main(){ cin>>n; for (int i=1;i<=n;i++) cin>>a[i]; int left=0,right=n; while (left+1<right){ int mid=left+(right-left>>1); if (check(mid)) left=mid; else right=mid; } printf("%d\n",left); return 0; }
标签:cnt,return,头牛,Gift,int,USACO17DEC,Takers,now,check From: https://www.cnblogs.com/purple123/p/17996972