首页 > 代码库 > hdu 4726 Kia's Calculation (贪心)

hdu 4726 Kia's Calculation (贪心)

# include <stdio.h>
# include <algorithm>
# include <string.h>
using namespace std;
char a[1000010],b[1000010];
int a1[1000010],b1[1000010],cot[1000010];
int vis1[1000010],vis2[1000010];
int main()
{
	
	int t,i,len,ans,flag,j,k;
	while(~scanf("%d",&t))
	{
		int ans=0;
		while(t--)
		{
			scanf("%s %s",a,b);
			memset(vis1,0,sizeof(vis1));
            memset(vis2,0,sizeof(vis2));
			len=strlen(a);
			for(i=0;i<len;i++)
			{
				vis1[a[i]-'0']++;
				vis2[b[i]-'0']++;
			}
			if(len==1)
			{
				printf("Case #%d: %d\n",++ans,(a[0]-'0'+b[0]-'0')%10);
			}
			else
			{
				printf("Case #%d: ",++ans);
				//首位处理
                for(i=9;i>=0;i--)//从大的树取起
				{
					flag=0;
					for(j=1;j<=9;j++)//没有前导零
					{
						int kk=(10+i-j)%10;
						if(kk==0)
							continue;
						if(vis1[j]&&vis2[kk])
						{
							vis1[j]--;
							vis2[kk]--;
							cot[0]=i;
							flag=1;
							break;
						}
					}
					if(flag)
						break;
				}
				if(cot[0]==0)//最大为零
				{
					printf("0\n");
				}
				else
				{
					for(i=1;i<len;i++)
					{
						for(j=9;j>=0;j--)
						{
							flag=0;
							for(k=0;k<=9;k++)
							{
								int kk=(10+j-k)%10;
								if(vis1[k]&&vis2[kk])
								{
									vis1[k]--;
									vis2[kk]--;
									cot[i]=j;
									flag=1;
									break;
								}
							}
							if(flag)
								break;
						}
					}
					for(i=0;i<len;i++)
					{
						printf("%d",cot[i]);
					}
					printf("\n");
				}

			}
		}
		return 0;
	}
}