Kia's Calculation(hdu 4726)
程序员文章站
2022-06-13 15:24:00
...
这题在寒假的贪心专题里出现过,不过当时不会,今天看到一位大神的博客……自己去敲了一波,不过我用的string输入(看到T<=25,怕内存超才用的),结果超时,换成char[]才过.......
ps:最高位特殊处理,后面那些只有0~9,用两个整型数组存出现次数,然后按数位依次凑9~0……
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int x[maxn],y[maxn],ans[maxn];
char a[maxn],b[maxn];
int main()
{
int t,kcase=0;
scanf("%d",&t);
while(t--)
{
scanf("%s%s",a,b);
int n=strlen(a);
if(n==1)
{
printf("Case #%d: %d\n",++kcase,(a[0]-'0'+b[0]-'0')%10);
continue;
}
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
for(int i=0;i<n;i++)
{
x[a[i]-'0']++;
y[b[i]-'0']++;
}
int x1=0,y1=0,ttt=-1;
for(int i=1; i<=9; i++)
for(int j=1; j<=9; j++)
if(x[i]&&y[j]&&((i+j)%10)>ttt)
{
x1=i;
y1=j;
ttt=(x1+y1)%10;
}
x[x1]--;
y[y1]--;
int cnt=0;
ans[cnt++]=(x1+y1)%10;
for(int p=9;p>=0;p--)
{
for(int i=0;i<=9;i++)
{
if(x[i])
{
if(i<=p)
{
int j=p-i;
int k=min(x[i],y[j]);
x[i]-=k;
y[j]-=k;
while(k--) ans[cnt++]=p;
}
int j=10+p-i;
if(j>9) continue;
int k=min(x[i],y[j]);
x[i]-=k,y[j]-=k;
while(k--) ans[cnt++]=p;
}
}
}
int s=0;
while(s<cnt-1&&ans[s]==0) s++;
printf("Case #%d: ",++kcase);
for(int i=s;i<cnt;i++) printf("%d",ans[i]);
printf("\n");
}
return 0;
}