「Test」第一饭堂

题意：一个有 $N(N\le 100000)$ 位数字的整数，如果有不小于 $K$ 个数位完全相同，那么这个数被认为是漂亮的。现在给你一个 $N$ 位数字的数，改变其中的一些数字使它变漂亮，改变一位数字的花费为改前和改后数字差的绝对值。现在求出改变的最小花费，同时给出字典序最小的修改方案。

一道贪心题。

首先发现 $N$ 的范围比较大，因此枚举要改哪些数是会超时的。我们设改变后 $K$ 个数位完全相同的那个数为 $p$，可以发现 $p\in [0,9]$，只有 $10$ 种情况，于是我们枚举 $p$，计算花费。

我们建立一个结构体，存储每个数位改变的花费，位置，初始值和最终值。枚举 $p$ 时先更新结构体，然后按花费从小到大排序(如果相同就按位置对初始和最终值排序，保证字典序最小)，计算花费取最小，同时保存修改方案(因为保存了位置)。

时间复杂度 $O(n\log n)$

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=100101;
int n,k,money=INF;
char s[maxn],ans[maxn];
struct node
{
	int cnt;//花费
	int id;//位置
	int f;//初始值
	int e;//最终值
}q[maxn];
int cmp(node a,node b)
{
	if(a.cnt!=b.cnt)
		return a.cnt<b.cnt;
	else
	{
		if(a.id<b.id)
			return a.e<a.f;
		else
			return b.e>b.f;
	}
}
int main()
{
	freopen("canteen.in","r",stdin);
	freopen("canteen.out","w",stdout);
	scanf("%d%d\n",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%c",&s[i]);
	for(int i=9;i>=0;i--)//枚举相同的数位
	{
		int r=i;
		for(int j=1;j<=n;j++)
		{
			q[j].cnt=abs(i-(s[j]-'0'));
			q[j].id=j;
			q[j].f=s[j]-'0';
			q[j].e=i;
		}
		sort(q+1,q+n+1,cmp);
		int p=0;
		for(int i=1;i<=k;i++)
			p+=q[i].cnt;
		if(p<=money)
		{
			money=p;
			for(int j=1;j<=n;j++)
				ans[j]=s[j];
			for(int j=1;j<=k;j++)
				ans[q[j].id]=r+'0';
		}
	}
	printf("%d\n",money);
	for(int i=1;i<=n;i++)
		printf("%c",ans[i]);
	return 0;
}