学步园

CF 118C

    这个题目可以暴力枚举变成0~9的情况，但究竟优先变哪一个位置需要分情况进行讨论，因此可以先按优先级将位置进行排序，依次改变该位置上的数字即可。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int number, a[10010], b[11][10010], sum[11], r[10010];
char str[10010];
int cmp(const void *_p, const void *_q)
{
int *p = (int *)_p;
int *q = (int *)_q;
if(abs(a[*p] - number) == abs(a[*q] - number))
    {
if(a[*p] == a[*q])
        {
if(number > a[*p])
return *q - *p;
else
return *p - *q;
        }
else
        {
if(number < a[*p] && number < a[*q])
return *p - *q;
else if(number > a[*p] && number > a[*q])
return *q - *p;
else
            {
if(a[*p] > a[*q])
return -1;
else
return 1;
            }
        }
    }
else
return abs(a[*p] - number) - abs(a[*q] - number);
}
int main()
{
int i, j, n, k, flag , cost;
while(scanf("%d%d", &n, &k) == 2)
    {
        scanf("%s", str);
for(i = 0; i < n; i ++)
            a[i] = str[i] - '0';
        cost = 1000000000;
for(i = 0; i < 10; i ++)
        {
for(j = 0; j < n; j ++)
                r[j] = j;
            number = i;
            qsort(r, n, sizeof(r[0]), cmp);
            sum[i] = 0;
int ok = 0,num = 0;
for(j = 0; j < n; j ++)
            {
if(num == k)
                    ok = 1;
if(!ok)
                {
                    b[i][r[j]] = i;
                    sum[i] += abs(number - a[r[j]]);
                    num ++;
                }
else
                    b[i][r[j]] = a[r[j]];
            }
if(sum[i] < cost)
            {
                cost = sum[i];
                flag = i;
            }
else if(sum[i] == cost)
            {
int t = 0;
for(j = 0; j < n; j ++)
if(b[i][j] != b[flag][j])
                    {
if(b[i][j] < b[flag][j])
                            t = 1;
break;
                    }
if(t)
                {
                    cost = sum[i];
                    flag = i;
                }
            }
        }
        printf("%d\n", cost);
for(i = 0; i < n; i ++)
            printf("%d", b[flag][i]);
        printf("\n");
    }
return 0;
}