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; } -
6
zt大佬太强了%%%
我模拟赛的时候甚至二分策略还错了,没想到对的策略。甚至连单调性都不能保证,也是唐完了。补完题来写一下二分的nlogn做法吧(可能下次看到这个题就是加强数据然后用zt大佬的解做了QwQ)
正文:
首先就是看数据 1e5 所以 n方 模拟肯定不行,就考虑n/nlogn做法,我这种彩笔肯定是想不出zt那种n做法的,所以先考虑nlogn,nlogn算法总共不多,稍微想想也能猜出来是二分加遍历。但是具体怎么遍历呢,二分条件又是什么(我就卡在这)
我们要知道,因为一个牛拿不到那一定是前面的牛互相纠缠(也不一定是所有,可能有一些已经跳出去但是剩下的纠缠了),轮不到他,而他前面的牛纠缠轮不到他,就更轮不到他后面的了。单调性就出现了 所以这道题的二分答案也呼之欲出了——二分第一个轮不到的牛的位置
那么知道了二分方案的话接下来就是check()了怎么样才能判断这个牛能不能轮到他呢 我们的c数组是用来存储这头牛拿完后会去到多少牛前面,那我们拿 - 就代表着他拿完后会到哪个位置,设这个值为bi(蒟蒻不会写角标喵) 因为一个牛想拿到,就必须让其他所有牛到它后面去,但是挨个模拟又实在过于麻烦怎么办? 考虑最优:最大的牛在最前面,然后往后顺延,如果你这个就到不了二分的这个值的后面,那就代表着这个值是领不到的,当然如果可以的话你这个就会到二分答案的后面
具体的就看代码ba~
#include<bits/stdc++.h> using namespace std; int n; int c[100005],b[100005]; void lhhsyn(){ ios::sync_with_stdio(false); cin.tie(0); } bool cmp(int a,int b){ return a>b; } bool solve(int x){ for(int i=1;i<x;i++) b[i]=c[i]; sort(b+1,b+x,cmp); int tmp=x;//领完需要到的位置 for(int i=1;i<x;i++){ if(b[i]<tmp) return 0; tmp--;//因为到这个答案的后面了所以下一个需要到的位置就少一 } return 1; } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>c[i]; c[i]=n-c[i]; } int l=1,r=n; while(l<=r){ int mid=(l+r)/2; if(solve(mid)){ l=mid+1; } else r=mid-1; } cout<<n-l+1; return 0; }麻烦点个赞喵~
-
4
平平无奇的二分做法,带 log。
楼上 zhengt 大佬有 O(n) 做法。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int a[N], b[N], n; bool c(int u) { for(int i=1; i<u; i++) b[i] = a[i]; sort(b + 1, b + u); int t = n - u; for(int i=1; i<u; i++) { if(b[i] > t) return 0; t++; } return 1; } int main() { ios :: sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n; for(int i=1; i<=n; i++) cin >> a[i]; int l = 1, r = n; while(l <= r) { int m = (l + r) >> 1; if(c(m)) l = m + 1; else r = m - 1; } cout << n - r << '\n'; return 0; }
- 1
信息
- ID
- 950
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 33
- 已通过
- 13
- 上传者