AT ARC B题 大样例没过,求助
  • 板块学术版
  • 楼主Expert_Dream
  • 当前回复9
  • 已保存回复9
  • 发布时间2023/10/8 22:00
  • 上次更新2023/11/2 14:52:01
查看原帖
AT ARC B题 大样例没过,求助
768530
Expert_Dream楼主2023/10/8 22:00
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fir first
#define se second
#define ull unsigned long long
#define endl "\n"
using namespace std;
const int N = 2e5+5;
int n,a,b,c;
int s[N];int ans;
struct node{
	int s,id;
}d1[N],d2[N],d3[N];
bool cmp(node a,node b){
	return a.s < b.s;
}
void run(int x,int y,int z){
	int res=1e18;
	for(int i = 1;i <= n;i++){
		d1[i].s = (s[i]%x==0)?0:(x-s[i]%x);
		d1[i].id=i;
//		cout<<d1[i].s<<" "<<d1[i].id<<endl;
	}
	for(int i = 1;i <= n;i++){
		d2[i].s = (s[i]%y==0)?0:(y-s[i]%y);
		d2[i].id=i;
//		cout<<d2[i].s<<" "<<d2[i].id<<endl;
	}
	for(int i = 1;i <= n;i++){
		d3[i].s = (s[i]%z==0)?0:(z-s[i]%z);
		d3[i].id=i;
//		cout<<d3[i].s<<" "<<d3[i].id<<endl;
	}
	sort(d1+1,d1+1+n,cmp);
	sort(d2+1,d2+1+n,cmp);
	sort(d3+1,d3+1+n,cmp);
	
	vector<pair<pair<int,int>,int> > ve;
	for(int i =1 ;i <= 3;i++) ve.push_back({{d1[i].s,d1[i].id},1});
	for(int i =1 ;i <= 3;i++) ve.push_back({{d2[i].s,d2[i].id},2});
	for(int i =1 ;i <= 3;i++) ve.push_back({{d3[i].s,d3[i].id},3});
//	for(auto it:ve) cout<<it.first <<" "<<it.second<<endl;
//	int la,lb,lc;
	for(int i = 0 ;i < ve.size();i++){
		for(int j = 0 ;j < ve.size();j++){
			if(i==j) continue;
			for(int k = 0 ;k < ve.size();k++){
				if(i==k||j==k) continue;
//				cout<<"x";
				if(ve[i].second != ve[j].second &&
				 ve[j].second != ve[k].second && 
				 ve[i].second!=ve[k].second && 
				 ve[i].fir.second != ve[j].fir.second && 
				 ve[j].fir.second != ve[k].fir.second &&
				 ve[i].fir.second!=ve[k].fir.second){
//					cout<<"y";
					res=min(res,ve[i].first.fir+ve[j].first.fir+ve[k].fir.first);
				}
			}
		}
	}
//	cout<<x<<" "<<y<<" "<<z<<" "<<res<<endl;
//	cout<<la<<" "<<lb<<" "<<lc<<endl;
	ans=min(ans,res);
}
signed main(){
	cin >> n >> a >> b >> c;
	for(int i = 1;i <= n;i++){
		scanf("%lld",&s[i]);
	}
	
	ans=1e18;
	run(a,b,c);
	run(a/__gcd(a,b)*b,b/__gcd(c,b)*c,1);
	run(a/__gcd(a,c)*c,a/__gcd(a,b)*b,1);
	run(a/__gcd(a,c)*c,b/__gcd(c,b)*c,1);
	run(a/__gcd(a,b)*b,c,1);
	run(a/__gcd(a,c)*c,b,1);
	run(c/__gcd(c,b)*b,a,1);
	int abc=__gcd(__gcd(a,b),c);
	while(abc!=1){
		if(a%abc==0) a/=abc;
		else if(b%abc==0) b/=abc;
		else if(c%abc==0) c/=abc;
		else break;
		abc=__gcd(__gcd(a,b),c);
	}
	run(a*b*c,1,1);
	cout<<ans;
	
	
	
	return 0;
}
2023/10/8 22:00
加载中...