3 条题解

  • 6
    @ 2026-10-28 9:17:33

    zt大佬太强了%%%

    我模拟赛的时候甚至二分策略还错了,没想到对的策略。甚至连单调性都不能保证,也是唐完了。补完题来写一下二分的nlogn做法吧(可能下次看到这个题就是加强数据然后用zt大佬的解做了QwQ)

    正文:

    首先就是看数据 1e5 所以 n方 模拟肯定不行,就考虑n/nlogn做法,我这种彩笔肯定是想不出zt那种n做法的,所以先考虑nlogn,nlogn算法总共不多,稍微想想也能猜出来是二分加遍历。但是具体怎么遍历呢,二分条件又是什么(我就卡在这)

    我们要知道,因为一个牛拿不到那一定是前面的牛互相纠缠(也不一定是所有,可能有一些已经跳出去但是剩下的纠缠了),轮不到他,而他前面的牛纠缠轮不到他,就更轮不到他后面的了。单调性就出现了 所以这道题的二分答案也呼之欲出了——二分第一个轮不到的牛的位置

    那么知道了二分方案的话接下来就是check()了怎么样才能判断这个牛能不能轮到他呢 我们的c数组是用来存储这头牛拿完后会去到多少牛前面,那我们拿 nn - cici就代表着他拿完后会到哪个位置,设这个值为bi(蒟蒻不会写角标喵) 因为一个牛想拿到,就必须让其他所有牛到它后面去,但是挨个模拟又实在过于麻烦怎么办? 考虑最优:bibi最大的牛在最前面,然后往后顺延,如果你这个就到不了二分的这个值的后面,那就代表着这个值是领不到的,当然如果可以的话你这个就会到二分答案的后面

    具体的就看代码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;
    } 
    
    

    麻烦点个赞喵~

    • @ 2026-10-28 9:21:16

      质量很高的题解,顶上去。

    • @ 2026-10-28 9:24:57

      Luogu 管理员:滥用标题行,不给过。

    • @ 2026-10-28 9:28:08

      老大老大,我们写题解真的可以提高自己对题目的理解程度吗

    • @ 2026-10-28 9:28:49

      @ 神了

    • @ 2026-10-28 9:37:25

      我后来发现好像正着写不搞b数组好像也行,就是反过来,只能说看个人喜好,我觉得还是b的回到对应名更像人类思维一点

信息

ID
950
时间
1000ms
内存
256MiB
难度
6
标签
(无)
递交数
33
已通过
13
上传者