关于本题的疑惑
查看原帖
关于本题的疑惑
368791
FL_sleake楼主2023/12/16 08:34

当两种奇数巧克力分别向偶数巧克力配对时,有可能出现匹配到同一块巧克力的情况,这时候其中一种奇数巧克力就应该匹配另一块巧克力。

然而为什么如下的代码直接进行匹配取min可以通过?

数据造的太水了吗

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,cnt1=0x3f3f3f3f3f3f3f3f,cnt2=0x3f3f3f3f3f3f3f3f;
multiset<int> R,G,B;
signed main(){
	cin>>n;
	for(int i=1;i<=2*n;i++){
		int x;
		char c;
		cin>>x>>c;
		if(c=='R') R.insert(x);
		else if(c=='G') G.insert(x);
		else B.insert(x);
	}
	int flg=(R.size()%2)+(G.size()%2)+(B.size()%2),ans=0x3f3f3f3f3f3f3f3f;
	if(!flg){
		cout<<"0"<<endl;
		return 0;
	}
	if(R.size()%2&&B.size()%2) swap(G,B);
	else if(G.size()%2&&B.size()%2) swap(R,B);
	for(int x:R){
		auto y=G.lower_bound(x);
		if(y!=G.end()) ans=min(ans,abs(x-*y));
		if(y!=G.begin()) y--,ans=min(ans,abs(x-*y));
	}
	for(int x:R){
		auto y=B.lower_bound(x);
		if(y!=B.end()) cnt1=min(cnt1,abs(x-*y));
		if(y!=B.begin()) y--,cnt1=min(cnt1,abs(x-*y));
	}
	for(int x:G){
		auto y=B.lower_bound(x);
		if(y!=B.end()) cnt2=min(cnt2,abs(x-*y));
		if(y!=B.begin()) y--,cnt2=min(cnt2,abs(x-*y));
	}
	cout<<min(ans,cnt1+cnt2)<<endl;
	return 0;
}
2023/12/16 08:34
加载中...