J - Min Number FZU - 2111——桶思想深化

冷不防 2022-06-16 02:16 135阅读 0赞

Think:  
1题意：给出一个高位数的数，交换有限次数，且首位交换后不能为零，求交换后所得到的最小数值  
2自己估计的一下，暴力枚举基本超时，因此考虑是否可优化，进而尝试是否可结合桶思想，再添加限制判断条件或提前结束条件  
3反思：一开始交换步骤出现错误(再度初始化思考不全面)，导致Wrong Answer

[vjudge题目链接][vjudge]

以下为Wrong Answer代码——交换步骤再度初始化不完全

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    
    int a[14][1004], v[14];
    
    int main()
    {
        int T, m, i, j, k, t, cnt;
        char st1[1004];
        scanf("%d", &T);
        while(T--)
        {
            cnt = 0;
            memset(a, 0, sizeof(a));
            memset(v, 0, sizeof(v));
            scanf("%s %d", st1, &m);
            int len = strlen(st1);
            for(i = 0; i < len; i++)
            {
                t = st1[i]-'0';
                a[t][i] = 1;
                v[t]++;
            }
    
            if(cnt < m)
            {
                for(j = 1; j < 9; j++)
                {
                    if(v[j] && (j < st1[0]-'0' || st1[0] == '0'))
                    {
                        for(k = 0; k < 1004; k++)
                        {
                            if(a[j][k])
                            {
                                a[j][k] = 0;
                                st1[k] = st1[0];
                                st1[0] = j + '0';
                                cnt++;
                                break;
                            }
                        }
                        v[j]--;
                        break;
                    }
                }
            }
    
            for(i = 1; i < len; i++)
            {
                if(cnt >= m)
                    break;
                for(j = 0; j < 9; j++)
                {
                    if(v[j] && j < st1[i]-'0')
                    {
                        int flag = 0;
                        for(k = i+1; k < 1004; k++)
                        {
                            if(a[j][k])
                            {
                                a[j][k] = 0;
                                st1[k] = st1[i];
                                st1[i] = j + '0';
                                cnt++;
                                v[j]--;
                                flag = 1;
                                break;
                            }
                        }
                        if(flag)
                            break;
                    }
                }
            }
            printf("%s\n", st1);
        }
        return 0;
    }

以下为Accepted代码

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    
    int a[14][1004], v[14];
    
    int main()
    {
        int T, m, i, j, k, t, cnt;
        char st1[1004];
        scanf("%d", &T);
        while(T--)
        {
            cnt = 0;
            memset(a, 0, sizeof(a));
            memset(v, 0, sizeof(v));
            scanf("%s %d", st1, &m);
            int len = strlen(st1);
            for(i = 0; i < len; i++)
            {
                t = st1[i]-'0';
                a[t][i] = 1;
                v[t]++;
            }
    
            if(cnt < m)
            {
                for(j = 1; j < 9; j++)
                {
                    if(v[j] && (j < st1[0]-'0' || st1[0] == '0'))
                    {
                        for(k = 1; k < 1004; k++)
                        {
                            if(a[j][k])
                            {
                                a[j][k] = 0;
                                t = st1[0]-'0';
                                a[t][k] = 1;
                                st1[k] = st1[0];
                                st1[0] = j + '0';
                                cnt++;
                                v[j]--;
                                break;
                            }
                        }
                    }
                }
            }
    
            for(i = 1; i < len; i++)
            {
                if(cnt >= m)
                    break;
                for(j = 0; j < 9; j++)
                {
                    if(v[j] && j < st1[i]-'0')
                    {
                        int flag = 0;
                        for(k = i+1; k < 1004; k++)
                        {
                            if(a[j][k])
                            {
                                a[j][k] = 0;
                                t = st1[i]-'0';
                                a[t][k] = 1;
                                st1[k] = st1[i];
                                st1[i] = j + '0';
                                cnt++;
                                v[j]--;
                                flag = 1;
                                break;
                            }
                        }
                        if(flag)
                            break;
                    }
                }
            }
            printf("%s\n", st1);
        }
        return 0;
    }

[vjudge]: https://vjudge.net/contest/161868#problem/J