已知第一饭堂饭菜的价格有N位(坑爹吧!),如果一个价格有不小于K个数位完全相同,那么这个数字就被认为是漂亮的,否则这个数字被认为是不漂亮的。饭堂班长想改变其中一个饭菜的价格,改变价格中的一位需要花费一些钱,所需费用是这一位改变量之差的绝对值。
饭堂班长希望你能把这个价格变漂亮,求出最小费用,同时给出字典序最小的一个方案。
第1行:两个用空格隔开的数字N和K(2≤n≤10^4, 2≤k≤n)。
第2行:一个N位的数字表示原来的价格。
第1行:最小费用。
第2行:所求方案。
6 5
898196
4
888188
3 2
533
0
533
10 6
0001112223
3
0000002223
时间:1s 空间:256M 10%的数据:N≤5;
20%的数据:N≤10;
30%的数据:N≤18;
70%的数据:N≤500;
对于100%的数据,2≤N≤10000,2≤k≤n。
记录s(原价)中0~9的个数,然后从0开始贪心(贪最小字典序),每算出一种答案比较一次,以防出现非最优解的情况
代码:
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; string fin,s,tmp; int n,k,i,j,t,ans1,ans,a[10]; void change(string &s,int x,int y) { int i; if (x>y) for(int i=0; i<n; i++) if(s[i]==x+‘0‘) { t--; s[i]=y+‘0‘; ans1+=abs(y-x); if(!t) break; } if(x<y) for(int i=n-1; i>=0; i--) if(s[i]==x+‘0‘) { t--; s[i]=y+‘0‘; ans1+=abs(y-x); if(!t) break; } } int main() { scanf("%d%d",&n,&k); cin>>s; for(int i=0; i<n; i++) a[s[i]-‘0‘]++; ans=int(1e9); fin=s; for(int i=0; i<10; i++) { t=k-a[i],ans1=0; tmp=s; if (t>0) for(int j=1; j<=9; j++) { if(i+j<10) change(tmp,i+j,i); if(!t) break; if(i-j>=0) change(tmp,i-j,i); if(!t) break; } if(ans1<ans) { ans=ans1; fin=tmp; } else if(ans1==ans&&tmp<fin) fin=tmp; /*printf("%d\n",ans); cout<<fin<<endl;*/ } printf("%d\n",ans); cout<<fin<<endl; return 0; }
原文:https://www.cnblogs.com/mysh/p/11386450.html