ACM模版

描述

题解

水题不水，有坑。

思路炒鸡简单，首先我们记录下来 0∼9 每个数字的个数，然后枚举让 x 出现 k 次的最小花费。

这里先说第一个容易错的点儿，那就是当初始状态就满族时，直接特判最小花费为 0 ，按照原数输出；
第二个容易错的地方便是，数字的变更的贪心策略，假如说最优解释让 x 出现 k 次，那么我们需要先考虑将 x−i 和 x+i 变成 x ，然后是 x−i−1 和 x+i+1 变成 x ，如果说将 x−i 和 x+i 都变成 x 都不够 k 个，那么我们继续往两边查找，然而如果用不了这么多呢？我们究竟有限变 x−i 呢还是 x+i ，这里，我们采用正序一遍将 x+i 变成 x ，然后逆序一遍将 x−i 变成 x ，直到够为止，这样能保证一些情况字典序最小；
第三个容易错的地方便是，当最小花费相同时，并不是 x 越小字典序就越小，比如说， n=8,k=4,num=22294777 ，那么最小花费是 2 ，对应的方案有两种， 22292777 和 22274777 ，前者 x=2 后者是 x=7 ，但是很明显后者字典序更小，所以我们需要将两个串儿进行比较，不能单纯的保留最小 x <script type="math/tex" id="MathJax-Element-3926">x</script>。

大致就是这些，没毛病，没有其他的可能会错的地方了。

代码

#include <iostream>

using namespace std;

const int MAXN = 1e4 + 10;
const int MAX_DIG = 10;
const int INF = 0x3f3f3f3f;

int n, k;
int cnt[MAX_DIG];
int num[MAXN];
int A[MAXN], B[MAXN];

void get_AB(int tmp[], int tot)
{
    memcpy(tmp, num, sizeof(num));

    int K = k - cnt[tot];
    for (int i = 1; i < MAX_DIG && K; i++)
    {
        int l = tot - i, r = tot + i;
        for (int j = 0; j < n && K; j++)
        {
            if (tmp[j] == r)
            {
                tmp[j] = tot;
                K--;
            }
        }
        for (int j = n - 1; j >= 0 && K; j--)
        {
            if (tmp[j] == l)
            {
                tmp[j] = tot;
                K--;
            }
        }
    }
}

bool cmp_AB()
{
    for (int i = 0; i < n; i++)
    {
        if (A[i] > B[i])
        {
            return 1;
        }
        else if (A[i] < B[i])
        {
            return 0;
        }
    }

    return 0;
}

int main(int argc, const char * argv[])
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        scanf("%1d", num + i);
        cnt[num[i]]++;
    }

    for (int i = 0; i < MAX_DIG; i++)
    {
        if (cnt[i] >= k)
        {
            printf("0\n");
            for (int j = 0; j < n; j++)
            {
                printf("%d", num[j]);
            }
            putchar(10);

            return 0;
        }
    }

    int min_cost = INF;
    for (int i = 0; i < MAX_DIG; i++)
    {
        int tmp = 0, K = k - cnt[i];
        for (int j = 1; j < MAX_DIG; j++)
        {
            int l = i - j, r = i + j;
            if (l >= 0)
            {
                if (K > cnt[l])
                {
                    tmp += j * cnt[l];
                    K -= cnt[l];
                }
                else
                {
                    tmp += j * K;
                    K = 0;
                }
            }
            if (!K)
            {
                break;
            }

            if (r < MAX_DIG)
            {
                if (K > cnt[r])
                {
                    tmp += j * cnt[r];
                    K -= cnt[r];
                }
                else
                {
                    tmp += j * K;
                    K = 0;
                }
            }
            if (!K)
            {
                break;
            }
        }

        if (tmp < min_cost)
        {
            min_cost = tmp;

            get_AB(A, i);
        }
        else if (tmp == min_cost)
        {
            get_AB(B, i);

            if (cmp_AB())
            {
                swap(A, B);
            }
        }
    }

    printf("%d\n", min_cost);
    for (int i = 0; i < n; i++)
    {
        printf("%d", A[i]);
    }
    putchar(10);

    return 0;
}