codeforces 845B Luba And The Ticket(模拟)"/>
codeforces 845B Luba And The Ticket(模拟)
地址:
题意:有一串6位数的数字,每个数字可以变换成任意数字(0-9),变换最小个数数字使这串数字成为一个lucky数。
所谓lucky即这个6位数的前三位数字和与后三位数字和相等。
思路:有两种方法,一种是绝对的暴力,就是下面这一种,因为数据量特别小,所以n^6的复杂度也能通过。这种方法判断了每一种情况,如果前面和后面相等,那么就判断给定字符串有多少是与符合条件的6个数字是不同的。然后每次比较最小的改变个数。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{char s[15];scanf("%s",s);int res=6;for(int i=0;i<10;i++)for(int j=0;j<10;j++)for(int k=0;k<10;k++)for(int l=0;l<10;l++)for(int m=0;m<10;m++)for(int n=0;n<10;n++){if(i+j+k!=l+m+n)continue;int cnt=0;cnt+=(s[0]!=i+'0');cnt+=(s[1]!=j+'0');cnt+=(s[2]!=k+'0');cnt+=(s[3]!=l+'0');cnt+=(s[4]!=m+'0');cnt+=(s[5]!=n+'0');res=min(res,cnt);}return 0*printf("%d\n",res);
}
接下来是常规方法 ,模拟
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define eps 1e-8
using namespace std;
typedef long long ll;
const int maxn=2*1e5+5;
char a[8];
int b[8];
int c[8],sum1,sum2;
int da[8],xiao[8];
bool cmp(int x,int y)
{return x>y;
}
int main()
{scanf("%s",a);int t1=0,t2=0;for(int i=0; i<3; i++){b[i+1]=a[i]-'0';sum1+=b[i+1];da[t1++]=b[i+1];xiao[t2++]=9-b[i+1];}for(int i=3; i<6; i++){c[i+1]=a[i]-'0';sum2+=c[i+1];da[t1++]=9-c[i+1];xiao[t2++]=c[i+1];}sort(da,da+6,cmp);sort(xiao,xiao+6,cmp);if(sum1==sum2) printf("0\n");else if(sum1>sum2){int t=0;for(int i=0; i<6; i++){sum1-=da[i];t++;if(sum1<=sum2) break;}printf("%d\n",t);}else{int t=0;for(int i=0; i<6; i++){sum2-=xiao[i];t++;if(sum2<=sum1) break;}printf("%d\n",t);}return 0;
}
更多推荐
codeforces 845B Luba And The Ticket(模拟)
发布评论