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大佬

信息

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