CF 118C - Fancy Number 贪心+字符串处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<cstdio>
#include<iostream>
#include<string.h>
using namespace std;

const int N=10005;
int n,k,a[N],ta[N],ans;
int num[10],tnum[10];
char hehe[N]={'9'+1},tmp[N];
void xiugai(int d,int k,int num){
	strcpy(tmp,"");
	if(k>d){
		for(int i=0;i<n&&num!=0;i++)
			if(a[i]==k) ta[i]=d,num--;
	}
	else{
		for(int i=n-1;i>=0&&num!=0;i--)
			if(a[i]==k) ta[i]=d,num--;
	}
}
void make(int d){
	for(int i=0;i<n;i++)
		ta[i]=a[i];
	for(int i=0;i<10;i++){
		if(num[i]==tnum[i]) continue;
		else xiugai(d,i,num[i]-tnum[i]);
	}
	for(int i=0;i<n;i++)
		tmp[i]=ta[i]+'0';
}
int solve(int d,int need){
	int rst=0;
	for(int i=1;i<10;i++){
		if((d+i)<=9){
			if(num[d+i]>=need){
				rst+=i*need;
				tnum[d+i]-=need;
				break;
			}
			else{
				rst+=i*num[d+i];
				need-=num[d+i];
				tnum[d+i]=0;
			}
		}
		if((d-i)>=0){
			if(num[d-i]>=need){
				rst+=i*need;
				tnum[d-i]-=need;
				break;
			}
			else{
				rst+=i*num[d-i];
				need-=num[d-i];
				tnum[d-i]=0;
			}
		}
	}
	return rst;
}

int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++){
		scanf("%1d",&a[i]);
		num[a[i]]++;
	}
	ans=1e9;
	for(int i=0;i<10;i++){
		if(k-num[i]<=0){
			printf("0n");
			for(int i=0;i<n;i++)
				printf("%d",a[i]);
			return 0;
		}
		memcpy(tnum,num,sizeof num);
		int kk=solve(i,k-num[i]);
		//printf("%d--n",ans);
		if(ans>=kk){
			if(ans>kk){
				strcpy(hehe,"{");
				ans=kk;
			}
			make(i);
			//printf("%sn",tmp);
			if(strcmp(hehe,tmp)>0)
				strcpy(hehe,tmp);
		}
	}
	printf("%dn",ans);
	printf("%sn",hehe);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<cstdio>
#include<string.h>

const int N=10005;
char str[N],s[N],hehe[N];
int num[10],n,k,ans,cnt,tmin;

int main(){
	scanf("%d %d",&n,&k);
	scanf("%s",s);
	for(int i=0;s[i];i++)
		num[s[i]-'0']++;
	int ans=1e9;
	for(int dst=0;dst<10;dst++){//转换目标
		cnt=num[dst],tmin=0;
		memcpy(str,s,sizeof s);
		for(int d=1;d<10&&cnt<k;d++){//绝对值贪心
			if((dst+d)<10){//前面大的->d 字典序减小
				int s=dst+d,e=dst;
				for(int i=0;i<n&&cnt<k;i++){
					if(str[i]-'0'==s)
						str[i]=e+'0',cnt++,tmin+=d;
				}
			}
			if((dst-d)>=0){//后面小的->d 字典序增大
				int s=dst-d,e=dst;
				for(int i=n-1;i>=0&&cnt<k;i--){
					if(str[i]-'0'==s)
						str[i]=e+'0',cnt++,tmin+=d;
				}
			}
		}
		//printf("%d %s %sn",tmin,hehe,str);
		if(tmin<ans)
			ans=tmin,strcpy(hehe,str);
		else if(tmin==ans&&strcmp(hehe,str)>0)
			strcpy(hehe,str);
	}
	printf("%dn",ans);
	printf("%sn",hehe);
	return 0;
}