2 条题解

  • 1
    @ 2026-10-24 11:38:52

    急了,难道我真是贪心低手..

    对于 Ci=1C_i = 1 的数据,我们可以通过经典结论做出。对于每一个 WiW_i,找比 WiW_i 大的最小的 BiB_i。

    然后,剩下的部分,直接做就是对的。因为我们一定可以找到一个点 xx,使得从 xx 开始,按顺时针考虑每一个 BiB_i 不会有剩余,此时再使用上面的结论就是正确的。因为不会有比 xx 靠前的 WiW_i 会影响当前的 BiB_i。

    考虑如何找到点 xx。我的做法是把每个位置看成 -1,因为会消耗一匹马。记 cnti=∑1≤j≤n[Cj=i]cnt_i = \sum\limits_{1 \le j \le n} [C_j=i] ,一个位置的权值就是 cnti−1cnt_i -1。

    然后从 1 到 nn 扫一遍整个序列,找前缀和最小的点 xx,x+1x+1一定是一个合法起点。

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define psb push_back
    const int N=5e5+1000,inf=1e15;
    int n,c[N],a[N],b[N<<1];
    vector<int>vec[N];
    set<int>st;
    signed main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>c[i];
    		vec[c[i]].psb(i);
    	}
    	for(int i=1;i<=n;i++) cin>>b[i],b[i+n]=b[i];
    	for(int i=1;i<=n;i++) cin>>a[i];
    	int minn=n,mini=0,sum=0;
    	for(int i=1;i<=n;i++){
    		sum=sum-1+vec[i].size();
    		if(sum<minn){
    			minn=sum;mini=i;
    		}
    	}
    	int ans=0;
    	for(int i=mini+1;i<=mini+n;i++){
    		for(int x:vec[(i%n==0?n:i%n)]) st.insert(a[x]);
    		auto it=st.lower_bound(b[i]);
    		if(it==st.end()){
    			st.erase(st.lower_bound(-1));
    		}else{
    			ans++;
    			st.erase(it);
    		}
    	}cout<<ans;
    	return 0;
    } 
    

    信息

    ID
    941
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    45
    已通过
    4
    上传者