欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Kia's Calculation(hdu 4726)

程序员文章站 2022-06-13 15:24:00
...

这题在寒假的贪心专题里出现过,不过当时不会,今天看到一位大神的博客……自己去敲了一波,不过我用的string输入(看到T<=25,怕内存超才用的),结果超时,换成char[]才过.......

ps:最高位特殊处理,后面那些只有0~9,用两个整型数组存出现次数,然后按数位依次凑9~0……

Kia's Calculation(hdu 4726)

#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;
}

相关标签: 贪心 算法