链接：https://www.nowcoder.com/questionTerminal/005af31a10834b3688911463065ab47d
来源：牛客网
A 国的手机号码由且仅由 N 位十进制数字(0-9)组成。一个手机号码中有至少 K 位数字相同则被定义为靓号。A 国的手机号可以有前导零，比如 000123456 是一个合法的手机号。
小多想花钱将自己的手机号码修改为一个靓号。修改号码中的一个数字需要花费的金额为新数字与旧数字之间的差值。比如将 1 修改为 6 或 6 修改为 1 都需要花 5 块钱。
给出小多现在的手机号码，问将其修改成一个靓号，最少需要多少钱？
输入描述:
第一行包含2个整数 N、K，分别表示手机号码数字个数以及靓号至少有 K 个数字相同。
第二行包含 N 个字符，每个字符都是一个数字('0'-'9')，数字之间没有任何其他空白符。表示小多的手机号码。
数据范围：
2 <= K <= N <= 10000
输出描述:
第一行包含一个整数，表示修改成一个靓号，最少需要的金额。
第二行包含 N 个数字字符，表示最少花费修改的新手机号。若有多个靓号花费都最少，则输出字典序最小的靓号。
示例1
输入
6 5
787585
输出
4
777577
说明
花费为4的方案有两种：777577与777775，前者字典序更小。
是一道贪心求解的题。由于一共就10个数字，求每一位数字作为靓号的花费。例如对于787585这个号，n=6，k=5。首先判断设置5个9的情况，再针对设置每个数字到9的花费进行排序。这里利用了一个结构体，包含了当前数的在号码的位置，其初始值，其目标值，以及从初始值转换到目标值所需要的花费。将花费从小到大进行排序，对于花费一致的数，这里需要输出字典序最小的结果，因此当当前数比目标数小，优先处理后面的数。
****************************************************************************************************************
Code
#include<bits/stdc++.h>
using namespace std;
struct Node{
int cost,index,origin,target;
};
bool cmp(Node a,Node b){//这个比较方法挺重要的
if(a.cost!=b.cost)//目标就是花最小的钱，所以cost小的排在前面
return a.cost<b.cost;
if(a.index<b.index)//如果二者花费的钱一样多，则选择字典序小的在前面
return a.target<a.origin;//已知a的位数更高，若目标值又小于原来值，这样字典序更小。所以按找输入返回a,b，也就是a在前b在后。
if(a.index>b.index)//同理
return b.target>b.origin;
};
int main(){
int n,k;
cin>>n>>k;
string s;
cin>>s;
int arr[n];
for(int i=0;i<n;i++){
arr[i]=int(s[i]-'0');
}
Node px[n];
int sum=INT_MAX,t;
int res[10000]={0};
for(int i=0;i<=9;i++){//分别选择0,1,2,3,4.....等作为选择的重复数字
for(int j=0;j<n;j++){//选择过重复数字就应该进行计算，算出总的cost
px[j].cost=abs(arr[j]-i);//原值减去目标值就是需要花费的值
px[j].index=j;//为每一个Node的索引赋值
px[j].origin=arr[j];//为每一个Node的初值赋值
px[j].target=i;//为每一个Node的目标值赋值
}
sort(px,px+n,cmp);//排序，让花费少的Node排在前面
t=0;
for(int j=0;j<k;j++){//既然已经排过序了，那么就应该从序列中选出前K个需要的重复的个数
t += px[j].cost;//计算出选择该目标值作为重复数字需要的花费
}
if(t<sum){//如果出现比当前更好的解，则更新花费值，跟靓号
sum=t;
for(int j=0;j<n;j++){
res[j]=arr[j];
}
for(int j=0;j<k;j++){
res[px[j].index]=i;//注意在一个程序中尽量不要使用同一个变量，如果错了的话，查都不好查
}
}
}
cout<<sum<<endl;
for(int i=0;i<n;i++){
cout<<res[i];
}
return 0;
}
网友评论