2 条题解
-
1
急了,难道我真是贪心低手..
对于 的数据,我们可以通过经典结论做出。对于每一个 ,找比 大的最小的 。
然后,剩下的部分,直接做就是对的。因为我们一定可以找到一个点 ,使得从 开始,按顺时针考虑每一个 不会有剩余,此时再使用上面的结论就是正确的。因为不会有比 靠前的 会影响当前的 。
考虑如何找到点 。我的做法是把每个位置看成 -1,因为会消耗一匹马。记 ,一个位置的权值就是 。
然后从 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
- 上传者