P1852求助
查看原帖
P1852求助
518995
GUMIfans0626楼主2023/7/31 15:01

求助 25pts

谢谢各位了

#include<bits/stdc++.h>
using namespace std;
struct sss{
	int a,b,c;
	int tot;
}A,B;
sss pd(sss s1){
	if(s1.a>s1.b) swap(s1.a,s1.b);
	if(s1.a>s1.c) swap(s1.a,s1.c);
	if(s1.b>s1.c) swap(s1.b,s1.c);
	while(1){
		int d1=s1.b-s1.a; int d2=s1.c-s1.b;
		if(d1==d2) break;
		if(d1>d2){
			int d3=(d1-1)/d2;s1.tot+=d3;
			s1.b-=d3*d2;
			s1.c-=d3*d2;
		}else{
			int d3=(d2-1)/d1; s1.tot+=d3;
			s1.a+=d3*d1;
			s1.b+=d3*d1;
		}
	}
	return s1;
}
bool yes(sss s1,sss s2){
	if(s1.a==s2.a && s1.b==s2.b && s1.c==s2.c) return 1;
	return 0;
}
sss G(sss s1,int depth){
	if(s1.a>s1.b) swap(s1.a,s1.b);
	if(s1.a>s1.c) swap(s1.a,s1.c);
	if(s1.b>s1.c) swap(s1.b,s1.c);
	while(depth){
		int d1=s1.b-s1.a; int d2=s1.c-s1.b;
		if(d1==d2) break;
		if(d1>d2){
			int d3=min((d1-1)/d2,depth); depth-=d3;
			s1.b-=d3*d2;
			s1.c-=d3*d2;
		}else{
			int d3=min((d2-1)/d1,depth); depth-=d3;
			s1.a+=d3*d1;
			s1.b+=d3*d1;
		}
	}
	return s1;
}
int main(){
	cin>>A.a>>A.b>>A.c;
	cin>>B.a>>B.b>>B.c;
	sss A1=A; sss B1=B;
	A1=pd(A);B1=pd(B);
	if(!yes(A1,B1)){
		cout<<"NO"<<endl;
		return 0;
	}
	cout<<"YES"<<endl;
	A.tot=A1.tot;
	B.tot=B1.tot;
	if(A.tot<B.tot){
		swap(A.a,B.a);
		swap(A.b,B.b);
		swap(A.c,B.c);
		swap(A.tot,B.tot);
	}
	int ABS1=abs(A.tot-B.tot);
	G(A,ABS1);
	A.tot=B.tot;
	int l=0,r=A.tot;
	int ans=0;
	while(l<=r){
		int mid=(l+r)>>1;
		sss S1=A; sss S2=B;
		S1=G(S1,mid); S2=G(S2,mid);
		if(yes(S1,S2)){
			ans=mid; r=mid-1; 
		}else{
			l=mid+1;
		}
	}
	cout<<ans*2+ABS1;
	return 0;
}
2023/7/31 15:01
加载中...