- 赛马
30pts,wa求调
- @ 2026-10-24 11:44:37
贪心策略似乎是正确的,考虑断环成链后用 set 维护多余的马,所有的小样例都过了,但大样例没过。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f;
const int inff=0x3f3f3f3f3f3f3f3f;
const int N=1e6+5;
const int M=5e5+5;
const int mod=1e9+7;
int n,c[N],b[N],w[N];
int len[N];
vector<int> a[M];
set<int> se;
void fast(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
signed main(){
// freopen("ex.in","r",stdin);
// freopen("ex.out","w",stdout);
fast();
cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i];
len[c[i]]++;
a[c[i]].push_back(i);
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1;i<=n;i++){
cin>>w[i];
}
// for(int i=n+1;i<=2*n;i++){
// b[i]=b[i-n];
// }
int ans=0;
for(int i=1;i<=2*n;i++){
// cout<<i<<endl;
if(i<=n){
if(len[i]==1){
// cout<<'a'<<endl;
if(w[a[i][0]]>b[i]){
ans++;
}
// cout<<i<<' '<<w[a[i][0]]<<'a'<<endl;
len[i]=-1;
// cout<<ans<<' '<<'a'<<endl;
}
else if(len[i]>1){
// cout<<'x'<<endl;
sort(a[i].begin(),a[i].end());
// cout<<'y'<<endl;
// cout<<a[i][len[i]-1]<<' '<<w[a[i][len[i]-1]]<<' '<<i<<' '<<b[i]<<' '<<len[i]<<endl;
if(w[a[i][len[i]-1]]>b[i]){
int x=0;
// cout<<'z'<<endl;
for(x;x<len[i];x++){
// cout<<'w'<<endl;
if(w[a[i][x]]>b[i]){
break;
}
}
// cout<<'o'<<endl;
for(int j=0;j<len[i];j++){
if(j==x){
// cout<<'p'<<endl;
continue;
}
else{
// cout<<'q'<<endl;
se.insert(w[a[i][j]]);
}
}
// cout<<'r'<<endl;
ans++;
len[i]=-1;
}
else{
for(int j=1;j<len[i];j++){
se.insert(w[a[i][j]]);
}
// ans++;
len[i]=-1;
}
}
else if(len[i]==0){
// cout<<'c'<<endl;
if(se.empty()){
continue;
}
else{
len[i]=-1;
if(*--se.end()>b[i]){
// cout<<'f'<<endl;
auto x=se.upper_bound(b[i]);
// cout<<'g'<<endl;
se.erase(x);
ans++;
}
else{
se.erase(se.begin());
}
}
}
}
else{
i=i-n;
if(len[i]==-1){
i+=n;
continue;
}
if(len[i]==1){
if(w[a[i][0]]>b[i]){
ans++;
}
len[i]=-1;
}
else if(len[i]>1){
sort(a[i].begin(),a[i].end());
if(w[a[i][len[i]-1]]>b[i]){
int x=0;
for(x;x<len[i];x++){
if(w[a[i][x]]>b[i]){
break;
}
}
for(int j=0;j<len[i];j++){
if(j==x){
continue;
}
else{
se.insert(w[a[i][j]]);
}
}
ans++;
len[i]=-1;
}
else{
for(int j=1;j<len[i];j++){
se.insert(w[a[i][j]]);
}
// ans++;
len[i]=-1;
}
}
else if(len[i]==0){
if(se.empty()){
i=i+n;
continue;
}
else{
len[i]=-1;
if(*--se.end()>b[i]){
auto x=se.upper_bound(b[i]);
se.erase(x);
ans++;
}
else{
se.erase(se.begin());
}
}
}
i=i+n;
// cout<<i<<endl;
}
// cout<<i<<' '<<ans<<'\n';
}
cout<<ans;
return 0;
}
1 條評論
-
caohongxuan LV 8 @ 2026-10-26 8:30:15已修改
- 1
資訊
- ID
- 941
- 時間
- 1000ms
- 記憶體
- 256MiB
- 難度
- 9
- 标签
- (無)
- 遞交數
- 45
- 已通過
- 4
- 上傳者