3 条题解

  • 7
    @ 2026-10-27 12:36:54

    O(n)O(n) 做法。

    首先记 bib_i 为 n−1−cin-1-c_i,表示这头牛收到礼物之后会往后退几步。

    然后可以观察到,如果前面的贪婪的牛太多,会导致只有一个前缀的牛能领到礼物。

    而如果贪婪的牛很少,后面的牛仍然能被它们放进来,所以能领到礼物的牛不一定很少。

    具体地,如果某个前缀有 ii 头牛的 bi≤i−1b_i \le i - 1,则该前缀以外的牛都不能领取礼物。

    所以我们可以枚举 ii,然后线段树二分求这个最小前缀,是 O(nlog⁡n)O(n \log n) 的。

    我赛时写的这个做法。

    然后我们可以发现最小前缀单调不增,所以我们直接考虑最小前缀能否减少。

    这样是 O(n)O(n) 的,代码很短。

    #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;
    }
    
    • @ 2026-10-28 9:37:54

      膜拜zt大佬

  • 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的回到对应名更像人类思维一点

  • 4
    @ 2026-10-28 8:57:18

    平平无奇的二分做法,带 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;
    }
    
    • @ 2026-10-28 8:58:28

      建议加强到 1e7 卡掉我的做法。

  • 1

信息

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