3 条题解
-
7
做法。
首先记 为 ,表示这头牛收到礼物之后会往后退几步。
然后可以观察到,如果前面的贪婪的牛太多,会导致只有一个前缀的牛能领到礼物。
而如果贪婪的牛很少,后面的牛仍然能被它们放进来,所以能领到礼物的牛不一定很少。
具体地,如果某个前缀有 头牛的 ,则该前缀以外的牛都不能领取礼物。
所以我们可以枚举 ,然后线段树二分求这个最小前缀,是 的。
我赛时写的这个做法。
然后我们可以发现最小前缀单调不增,所以我们直接考虑最小前缀能否减少。
这样是 的,代码很短。
#include<bits/stdc++.h> using namespace std; const int N=1e5+1000; int n,c[N],usd[N]; vector<int> vec[N]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=1;i<=n;i++) cin>>c[i],vec[n-1-c[i]].push_back(i); int ans=n,cnt=0; for(int i=0;i<n;i++){ for(int id:vec[i]) if(id<=ans) usd[id]=1,cnt++; while(cnt-usd[ans]>=i+1) cnt-=usd[ans--]; }cout<<n-ans; return 0; }
信息
- ID
- 950
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 33
- 已通过
- 13
- 上传者