3 条题解
-
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; }麻烦点个赞喵~
信息
- ID
- 950
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 33
- 已通过
- 13
- 上传者