您当前处于兼容模式。某些功能在此模式下不可用。我们强烈建议在现代浏览器上切换为标准模式以获得更好的体验。 标准模式 隱藏

贪心策略似乎是正确的,考虑断环成链后用 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 條評論

  • 1

資訊

ID
941
時間
1000ms
記憶體
256MiB
難度
9
标签
(無)
遞交數
45
已通過
4
上傳者