Luba And The Ticket (CodeForces"/>
Luba And The Ticket (CodeForces
题意很明确,可以更换6个数字,使得 sum[1~3]==sum[4~6];
有三种方法,第一种暴力,枚举,和技巧。
一、暴力型:
#include<bits/stdc++.h>
using namespace std;
int main()
{char a[7];scanf("%s",a);int cnt=3;if(a[0]+a[1]+a[2]==a[3]+a[4]+a[5]){printf("0\n");return 0;}int a1,a2,a3,a4,a5,a6;a1=a[0]-'0';a2=a[1]-'0';a3=a[2]-'0';a4=a[3]-'0';a5=a[4]-'0';a6=a[5]-'0';for(int i1=0;i1<10;i1++){for(int i2=0;i2<10;i2++){for(int i3=0;i3<10;i3++){for(int i4=0;i4<10;i4++){for(int i5=0;i5<10;i5++){for(int i6=0;i6<10;i6++){if(i1+i2+i3!=i4+i5+i6)continue;int ans=0;ans+=(a[0]-'0'!=i1);ans+=(a[1]-'0'!=i2);ans+=(a[2]-'0'!=i3);ans+=(a[3]-'0'!=i4);ans+=(a[4]-'0'!=i5);ans+=(a[5]-'0'!=i6);cnt=min(ans,cnt);}}}}}}printf("%d\n",cnt);return 0;
}
二、枚举型:
#include<bits/stdc++.h>
using namespace std;
int maxz(int a,int b,int c)
{return max(a,b)>c?max(a,b):c;
}
int minz(int a,int b,int c)
{return min(a,b)<c?min(a,b):c;
}
int diff(int a,int b)
{return abs(a-b);
}
int mid(int a,int b,int c)
{int d[3]={a,b,c};sort(d,d+3);return d[1];
}
int main()
{char a[7];cin>>a;int b[6];for(int i=0;i<6;i++){b[i]=a[i]-'0';}int sum1=b[0]+b[1]+b[2];int sum2=b[3]+b[4]+b[5];if(sum1==sum2){printf("0\n");return 0;}else if(diff(sum1,sum2)>18){printf("3\n");return 0;}else if(sum1>sum2&&(sum1-sum2<=9-minz(b[3],b[4],b[5])||sum1-sum2<=maxz(b[0],b[1],b[2]))){printf("1\n");return 0;}else if(sum1<sum2&&(sum2-sum1<=9-minz(b[0],b[1],b[2])||sum2-sum1<=maxz(b[3],b[4],b[5]))){printf("1\n");return 0;}else if(sum1>sum2&&diff(sum1,sum2)<=maxz(b[0],b[1],b[2])+9-minz(b[3],b[4],b[5])){printf("2\n");return 0;}else if(sum1<sum2&&diff(sum1,sum2)<=maxz(b[3],b[4],b[5])+9-minz(b[0],b[1],b[2])){printf("2\n");return 0;}else if(sum1>sum2&&diff(sum1,sum2)<=maxz(b[0],b[1],b[2])+mid(b[0],b[1],b[2])){printf("2\n");return 0;}else if(sum1>sum2&&diff(sum1,sum2)<=18-minz(b[3],b[4],b[5])-mid(b[3],b[4],b[5])){printf("2\n");return 0;}else if(sum2>sum1&&diff(sum1,sum2)<=maxz(b[3],b[4],b[5])+mid(b[3],b[4],b[5])){printf("2\n");return 0;}else if(sum2>sum1&&diff(sum1,sum2)<=18-minz(b[0],b[1],b[2])-mid(b[0],b[1],b[2])){printf("2\n");return 0;}else{printf("3\n");return 0;}}
三、技巧型:
#include<bits/stdc++.h>
using namespace std;
int cmp(int a,int b)
{return a>b;
}
int main()
{char s[7];cin>>s;int sum=0;int a[6];for(int i=0;i<6;i++){if(i<=2)sum+=s[i]-'0';elsesum-=s[i]-'0';}if(sum==0){return 0*printf("0\n");}else if(sum>0){for(int i=0;i<6;i++){if(i<3)a[i]=s[i]-'0';elsea[i]=9-(s[i]-'0');}}else{for(int i=0;i<6;i++){if(i<3)a[i]=9-(s[i]-'0');elsea[i]=s[i]-'0';}}sum=abs(sum);sort(a,a+6,cmp);/*for(int i=0;i<6;i++){printf("%d\n",a[i]);}*/for(int i=0;i<6;i++){if(sum-a[i]<=0){printf("%d\n",i+1);return 0;}elsesum-=a[i];}return 0;
}
更多推荐
Luba And The Ticket (CodeForces
发布评论