2 条题解
-
1
题解
为了洛谷写的,懒得改了,注意 敌人->黑马,己方->白马,力量值->速度
竞选最简单做法。
典型的田忌赛马问题,如果可以任意选对手,那么从大到小考虑每一个对手,维护一个当前己方力量值的集合。如果当前集合里有能打败当前对手的,就让最小的能打败他的人出战。否则直接让力量值最小的出去送死。不再证明其正确性。
在本题中,我们顺时针考虑每一个敌人,并维护己方力量值集合,按上述策略决策。
假设当前点不需要依赖他之前的点延后的人就能完成全部决斗,也就是从他开始,没有己方轮空的情况,那么从他开始枚举敌人就是正确的。
现在我们解决了决策的问题,我们只需要找到这个开头位置,一切就迎刃而解了。
具体地,因为涉及到取模,我们把操作转为 0-index 的,也就是令所有
a[i]--。考虑维护一个森林结构,对每一个 ,我们从 的根向 连一条边,显然在最后一次连边之前,所有点已经全部连通。
这时的局面可能是这样的:

考虑那个没有入度的点,设其为 ,这些边的意义可以认为是,从 开始顺时针枚举,可以在所有点对决。
显然 是一个合法的起点。
发现我们不需要真的维护这个环,只需要维护他的连通关系,这样就可以用并查集维护了。
容易做到 。
代码
#include<bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second int T,n,m; int a[501000],b[501000],c[501000]; int fa[501000]; void init(){ for(int i=0;i<n;i++) fa[i]=i; } int find(int x){ if(fa[x]==x) return x; return fa[x]=find(fa[x]); } int s; void merge(int i){ int x=find(i); if(find(i)==find((find(i)+1)%n)) s=(find(i)+1)%n; else fa[find(i)]=find((find(i)+1)%n); } vector<int> vec[501000]; set<int> st; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; init(); for(int i=0;i<n;i++){ cin>>c[i],c[i]--,merge(c[i]),vec[c[i]].push_back(i); } for(int i=0;i<n;i++){ cin>>b[i]; } for(int i=0;i<n;i++){ cin>>a[i]; } int i=s,ans=0; do{ for(int j:vec[i]) st.insert(a[j]); auto it=st.upper_bound(b[i]); if(it==st.end()) st.erase(st.begin()); else st.erase(it),ans++; i=(i+1)%n; }while(i!=s); cout<<ans<<'\n'; return 0; } -
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; }
- 1
信息
- ID
- 941
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 45
- 已通过
- 4
- 上传者