A 国的手机号码由且仅由 N 位十进制数字(0-9)组成。一个手机号码中有至少 K 位数字相同则被定义为靓号。A 国的手机号可以有前导零，比如 000123456 是一个合法的手机号。 小多想花钱将自己的手机号码修改为一个靓号。修改号码中的一个数字需要花费的金额为新数字与旧数字之间的差值。比如将 1 修改为 6 或 6 修改为 1 都需要花 5 块钱。 给出小多现在的手机号码，问将其修改成一个靓号，最少需要多少钱？
[编程题]选靓号
- 热度指数：5673 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
第一行包含2个整数 N、K，分别表示手机号码数字个数以及靓号至少有 K 个数字相同。
第二行包含 N 个字符，每个字符都是一个数字('0'-'9')，数字之间没有任何其他空白符。表示小多的手机号码。
数据范围：
2 <= K <= N <= 10000
输出描述:
第一行包含一个整数，表示修改成一个靓号，最少需要的金额。
第二行包含 N 个数字字符，表示最少花费修改的新手机号。若有多个靓号花费都最少，则输出字典序最小的靓号。
示例1
输入
6 5 787585
输出
4 777577
说明
花费为4的方案有两种：777577与777775，前者字典序更小。
package 选靓号;
import java.util.Scanner;
/*
* 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，前者字典序更小。
*/
/*
* 算法：最小代价优先的贪心算法
* 数据结构：字符串
* 字典序：
* 1）如果手机号中数字比最佳数字大的情况就从前往后改；
* 2）如果手机号中数字比最佳数字小的情况就从后往前改;
* 3）1、2顺序不能颠倒
*/
public class Main {
//得到0-9在原手机号中出现的次数
private static int[] getRepeatTimes(char[] phoneNum) {
int[] repeatTimes = new int[10];
for (int i = 0; i < phoneNum.length; i ++) {
repeatTimes[phoneNum[i] - '0'] ++;
}
return repeatTimes;
}
//最小代价优先的贪心算法
private static void GreedyMinCost(int phoneNumSize, int neededRepeatTimes, char[] phoneNum) {
int minCost = Integer.MAX_VALUE;//想要最小值，初值设置最大整数
char[] newPhoneNum = new char[phoneNumSize];
int[] repeatTimes = getRepeatTimes(phoneNum);
for (int currentNum = 0; currentNum < 10; currentNum ++) {
int restNeededRepeatTimes = neededRepeatTimes - repeatTimes[currentNum];
//初始可能重复数字次数就大于需求值
if (restNeededRepeatTimes <= 0) {
minCost = 0;
newPhoneNum = phoneNum;
break;
}
int currentNumCost = 0;
int upperLimitNum = currentNum + 1;
int lowerLimitNum = currentNum - 1;
char[] alternativePhoneNum = new char[phoneNumSize];
//alternativePhoneNum每次循环前都初始为phoneNum的复制
System.arraycopy(phoneNum, 0, alternativePhoneNum, 0, phoneNumSize);
while (restNeededRepeatTimes > 0) {
//如果手机号中数字比最佳数字大的情况就从前往后改
if (upperLimitNum < 10) {
for (int i = 0; i < phoneNumSize && restNeededRepeatTimes > 0; i ++) {
if (phoneNum[i] - '0' == upperLimitNum) {
currentNumCost += upperLimitNum - currentNum;
alternativePhoneNum[i] = (char)(currentNum + '0');
restNeededRepeatTimes --;
}
}
}
//如果手机号中数字比最佳数字小的情况就从后往前改
if (lowerLimitNum >= 0) {
for (int i = phoneNumSize - 1; i >= 0 && restNeededRepeatTimes > 0; i --) {
if (phoneNum[i] - '0' == lowerLimitNum) {
currentNumCost += currentNum - lowerLimitNum;
alternativePhoneNum[i] = (char)(currentNum + '0');
restNeededRepeatTimes --;
}
}
}
//扩大上下限
upperLimitNum ++;
lowerLimitNum --;
}
if (currentNumCost < minCost) {
minCost = currentNumCost;
newPhoneNum = alternativePhoneNum;
}
}
System.out.println(minCost);
System.out.println(newPhoneNum);
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int phoneNumSize = input.nextInt();
int neededRepeatTimes = input.nextInt();
//第二行的输入的手机号是字符串不是整数！输出也很方便，值运算时清除'0'的影响
char[] phoneNum = input.next().toCharArray();
input.close();
GreedyMinCost(phoneNumSize, neededRepeatTimes, phoneNum);
}
}
发表于 2020-03-10 10:44:02
回复(0)
"""
最小修改距离，
先找最小修改距离ans_cost下，相同的数字ans_num
再求以ans_num为修改目标，当修改值大于ans_num时从前往后修改，
当修改值小于ans_num时从后往前修改
"""
from collections import Counter
def distance(dic, k, t):
ret = 0
if dic[t] >= k: return ret
k -= dic[t]
for i in range(1, 10):
if t + i < 10:
if dic[t + i] >= k:
ret += i * k
return ret
else:
k -= dic[t + i]
ret += i * dic[t + i]
if t - i >= 0:
if dic[t - i] >= k:
ret += i * k
return ret
else:
k -= dic[t - i]
ret += i * dic[t - i]
def modify(s, dic, k, t):
if dic[t] >= k: return
k -= dic[t]
for i in range(1, 10):
if t + i < 10:
for j in range(len(s)):
if k == 0: return
if s[j] == t + i:
s[j] = t
k -= 1
if t - i >= 0:
for j in range(len(s) - 1, -1, -1):
if k == 0: return
if s[j] == t - i:
s[j] = t
k -= 1
if __name__ == "__main__":
n, k = map(int, input().strip().split())
s = list(map(int, list(input().strip())))
dic = Counter(s)
for i in range(10):
if i not in dic:
dic[i] = 0
ans_cost, ans_num = float("inf"), -1
for i in range(10):
tmp = distance(dic, k, i)
if ans_cost > tmp:
ans_cost = tmp
ans_num = i
modify(s, dic, k, ans_num)
print(ans_cost)
print(''.join(map(str, s)))
发表于 2019-07-17 21:23:53
回复(3)
思路：遍历0-9每一个数字，计算每一个数字出现k次时候的最小花费
细节：
1.计算过程中使用gap表示距离当前数字i的花费
2.因为要输出具体变化后的结果，所以需要考虑如何变化，如果要变化的值小于当前值，则从前往后替代，如果大于当前值，则从后往前替代（为了保证字典序最小）
from collections import Counter
n,k = map(int, input().split())
s = input()
d = Counter(list(map(int,s)))
res = float("inf")
ans = "A"
for i in range(10):
tmp_s = s
need = k - d[i]
cost = 0
gap = 1
while need > 0:
if i+gap <= 9:
if d[i+gap] < need:
tmp_s = tmp_s.replace(str(i + gap), str(i))
cost += d[i+gap] * gap
need -= d[i+gap]
else:
tmp_s = tmp_s.replace(str(i + gap), str(i), need)
cost += need * gap
break
if i - gap >= 0:
if d[i-gap] < need:
tmp_s =tmp_s.replace(str(i-gap), str(i))
cost += d[i-gap] * gap
need -= d[i-gap]
else:
tmp_s = tmp_s[::-1]
tmp_s = tmp_s.replace(str(i-gap), str(i), need)
tmp_s = tmp_s[::-1]
cost += need * gap
break
gap += 1
if cost < res:
ans = tmp_s
res = cost
elif cost == res and tmp_s < ans:
ans = tmp_s
print(res)
print(ans)
发表于 2019-07-12 15:22:35
回复(3)
#include <bits/stdc++.h>
using namespace std;
char str[10010];
int a[10010];
struct node {
int id;
int num;
int lf;
int target;
node(int id_, int num_, int lf_, int target_):id(id_), num(num_), lf(lf_), target(target_){}
bool operator < (const node a) {
if (num == a.num) {
if (lf == a.lf) {
if (target > lf) {
return id > a.id;
} else {
return id < a.id;
}
}
return lf > a.lf;
}
return num < a.num;
}
};
int main() {
int n, k;
int len;
int Min = INT_MAX;
string ret = "";
scanf("%d %d", &n, &k);
scanf("%s", str);
len = strlen(str);
for (int i = 0; i < len; i++) {
a[i] = (str[i] - '0');
}
for (int num = 0; num <= 9; num++) {
vector <node> vec;
vec.clear();
int cot = 0;
int sum = 0;
for (int i = 0; i < len; i++) {
if (a[i] != num) {
vec.push_back(node(i, abs(a[i] - num), a[i], num));
} else {
cot++;
}
}
sort(vec.begin(), vec.end());
for (int i = 0; i < k - cot; i++) {
sum += vec[i].num;
}
if (sum < Min) {
Min = sum;
ret = str;
for (int i = 0; i < k - cot; i++) {
ret[vec[i].id] = (num + '0');
}
} else if (sum == Min) {
string temp = str;
for (int i = 0; i < k -cot; i++) {
temp[vec[i].id] = (num + '0');
}
if (temp < ret) {
ret = temp;
}
}
}
cout << Min << "\n";
cout << ret << "\n";
return 0;
}
发表于 2019-11-23 15:04:49
回复(0)
#include<iostream>#include<algorithm>#include<string>#include <stdlib.h>#include<limits.h>usingnamespacestd;structnode{intconsume,num,target,ori;};intcmp(node n1, node n2){if(n1.consume!=n2.consume) returnn1.consume<n2.consume;if(n1.num<n2.num) returnn1.target<n1.ori;returnn2.target>n2.ori;}voidysy(int*num,intn,intk){node nx[n],ny[n];intcnt=INT_MAX,tmp;intres[n];for(inti=9;i>=0;--i){for(intj=0;j<n;++j){nx[j].consume=abs(num[j]-i);nx[j].num=j;nx[j].target=i;nx[j].ori=num[j];}sort(nx,nx+n,cmp);tmp=0;for(intp=0;p<k;++p){tmp+=nx[p].consume;}if(tmp<=cnt){cnt=tmp;for(intj=0;j<n;++j) res[j]=num[j];for(intp=0;p<k;++p) res[nx[p].num]=i;}}printf("%d\n",cnt);for(intj=0;j<n;++j) printf("%d",res[j]);}intmain(){intn,k;scanf("%d %d",&n,&k);charc[n];scanf("%s",c);intnum[n];for(inti=0;i<n;i++){num[i]=int(c[i]-'0');//printf("%c",char(num[i]-1));}ysy(num,n,k);}
发表于 2019-04-24 17:18:40
回复(1)
一楼的思路，写个我自己理解的注释。
整体思路是贪心算法，将0-9依次作为需要被改成重复k次的数字（即目标数字），然后修改不等于目标数字的其他数字并计算代价，最后将最小代价及其对应字典序最小的靓号输出。
需要注意的是：对于不等于目标数字的其他数字，为了得到字典序更小的号码，应该尽可能将前面比目标数字大的改小为目标数字 或 将后面比目标数字小的改大为目标数字。
选定一个数对，一个比目标数字大1作为上界，另一个比目标数字小1作为下界，遍历号码中的数字，对于比目标数字大的数，从前往后改，而对于比目标数字小的数，从后往前改。如果这一轮改完后，如果目标数字的重复数字还没有达到k次，就扩张上下界继续修改。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] strArr = br.readLine().trim().split(" ");
int n = Integer.parseInt(strArr[0]), k = Integer.parseInt(strArr[1]);
char[] phoneNum = br.readLine().trim().toCharArray();
solve(n, k, phoneNum);
}
private static void solve(int n, int k, char[] phoneNum) {
int minCost = Integer.MAX_VALUE;
char[] newPhoneNum = new char[n];
// 先得到原本号码中各数字出现的次数
int[] counter = getCounter(phoneNum);
for(int curNum = 0; curNum < 10; curNum ++) {
// 依次计算将数字curNum改到k次需要多大的代价
if(counter[curNum] >= k){
// 已经满足靓号要求
minCost = 0;
newPhoneNum = phoneNum;
break;
}
int curNumCost = 0;
int upperLimitNum = curNum + 1; // 将upperLimitNum改成curNum
int lowerLimitNum = curNum - 1; // 将lowerLimitNum改成curNum
char[] tempPhoneNum = Arrays.copyOfRange(phoneNum, 0, phoneNum.length);
// 还需要的重复次数
int remain = k - counter[curNum];
// 循环直至不再需要数字重复
while(remain > 0) {
// 比curNum大的数字从前往后改(尽量把前面的数改小，以保证字典序小)
if(upperLimitNum < 10) {
for(int i = 0; i < n && remain > 0; i ++) {
if(phoneNum[i] - '0' == upperLimitNum) {
curNumCost += upperLimitNum - curNum;
tempPhoneNum[i] = (char)(curNum + '0');
remain --;
}
}
}
// 比curNum小的数字从后往前改(尽量把后面的数改大，以保证字典序小)
if(lowerLimitNum >= 0) {
for(int i = n - 1; i >= 0 && remain > 0; i --) {
if(phoneNum[i] - '0' == lowerLimitNum) {
curNumCost += curNum - lowerLimitNum;
tempPhoneNum[i] = (char)(curNum + '0');
remain --;
}
}
}
// 如果改完了upperLimitNum和lowerLimitNum还没达到k次重复，就扩大上下限继续改
upperLimitNum ++;
lowerLimitNum --;
}
// 更新代价更小的靓号
if(curNumCost < minCost) {
minCost = curNumCost;
newPhoneNum = tempPhoneNum;
}
}
System.out.println(minCost);
System.out.println(newPhoneNum);
}
private static int[] getCounter(char[] phoneNum) {
int[] counter = new int[10];
for(int i = 0; i < phoneNum.length; i++)
counter[phoneNum[i] - '0'] ++;
return counter;
}
}
编辑于 2021-02-18 17:04:25
回复(0)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 10;
bool is_ok(int x){
if(x>=0&&x<=9) return true;
return false;
}
int Solve(int x, int *num, int k){//求数字i变为k个最少需要多少花费
int ans=0;
queue<int>que;
if(is_ok(x+1)) que.push(x+1);
if(is_ok(x-1)) que.push(x-1);
while(k>0){
int temp = que.front();
que.pop();
if(temp>x){//按照距离更新求最少花费
ans += min(num[temp], k)*(temp-x);
if(is_ok(temp+1)) que.push(temp+1);
} else{
ans += min(num[temp], k)*(x-temp);
if(is_ok(temp-1)) que.push(temp-1);
}
k -= min(num[temp], k);
}
return ans;
}
int main(){
int n, k, num[12], cost[12];
char s[MAXN];
while(~scanf("%d%d", &n, &k)){
for(int i=0; i<10; i++) num[i]=0, cost[i]=0;
scanf("%s", s);
bool flag = false;
for(int i=0; i<strlen(s); i++){
int temp = s[i]-'0';
num[temp]++;
if(num[temp]>=k){//不需要更改的情况 已经是靓号
flag = true;
printf("0\n%s\n", s);
break;
}
}
if(flag) continue;
for(int i=0; i<10; i++) cost[i]=Solve(i, num, k-num[i]);
int min_cost = 0x7f7f7f7f, id;//选出最佳靓数
for(int i=0; i<10; i++) if(cost[i]<min_cost) id=i, min_cost=cost[i];
vector<int>change_num;//按顺序存储可能需要改的数字
k -= num[id];//更新需要修改的数目
for(int i=1; i<=9; i++){
if(is_ok(id+i) && num[id+i]) change_num.push_back(id+i);
if(is_ok(id-i) && num[id-i]) change_num.push_back(id-i);
}
char ch = id + '0';//靓号
for(int i=0; i<change_num.size(); i++){
char tt = change_num[i]+'0';
if(change_num[i]>id){//大数换小数 从前往后
for(int j=0; j<strlen(s); j++){
if(s[j]==tt && k){
k--;s[j]=ch;
}
}
}else{
for(int j=strlen(s)-1; j>=0; j--){//小数换大数 从后往前
if(s[j]==tt && k){
k--;s[j]=ch;
}
}
}
}
printf("%d\n%s\n", cost[id], s);
}
return 0;
}
发表于 2020-07-23 02:02:33
回复(0)
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
//pdd 3找最修改数字最多为K个的最小花费问题
String[] arr = in.readLine().split(" ");
int N = Integer.valueOf(arr[0]);
int K = Integer.valueOf(arr[1]);
char[] cs = in.readLine().toCharArray();
int[] ns = new int[cs.length];
int[] count = new int[10];
for(int i=0;i<cs.length;i++){
ns[i] = Integer.parseInt(String.valueOf(cs[i]));
count[ns[i]]++;
}
int store = 0;
int ansCost = Integer.MAX_VALUE;//最小花费
int mid = -1;//选定的数字中心
for(int i=0;i<10;i++){
store = K - count[i];
int lstep = 1;
int rstep = 1;
int tmpCost = 0;
while (store > 0){//往左右两边搜索需要改变的数字
if(store != 0 && i+rstep<10){//先换右边字典序列更靠前
int minus = Math.min(store,count[i+rstep]);
store -= minus;
tmpCost += minus * rstep;
rstep++;
}
if(store != 0 && i-lstep>=0){
int minus = Math.min(store,count[i-lstep]);
store -= minus;
tmpCost += minus * lstep;
lstep++;
}
}
if(tmpCost < ansCost) {
ansCost = tmpCost;
mid = i;
}
}
//换取需要变动的字符串,为了换取后是最小的字典序列,先从左向右换取比中心值大的字符串,注意这里要先换完所有mid最近的数
//比如mid是 3 我要先把所有的4先换掉,因为要保证cost最小!!!再换所有的2,知道换的数目得到满足
store = K - count[mid];
int step = 1;
while(store > 0){
if(mid + step < 10){
for(int i=0;i<ns.length;i++){
if(ns[i] == mid+step){
ns[i] = mid;
store--;
if(store <= 0)break;
}
}
}
if(store <= 0)break;
if(mid - step >= 0){//这里要从右向左换!!!
for(int i=ns.length-1;i>=0;i--){
if(ns[i] == mid-step){
ns[i] = mid;
store--;
if(store <= 0)break;
}
}
}
step++;
}
System.out.println(ansCost);
for(int i=0;i<ns.length;i++){
System.out.print(ns[i]);
}
}
}
发表于 2020-04-12 12:28:12
回复(0)
import java.util.*;
public class Main {
int N, K;
// 存放数字对应的 index
List<Integer>[] buckets = new ArrayList[10];
String number;
int minPrice = Integer.MAX_VALUE;
List<String> res = new ArrayList<>();
// 17.19
public static void main(String[] args) {
Main m = new Main();
m.solution();
}
private void solution() {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
K = sc.nextInt();
sc.nextLine();
number = sc.nextLine();
for (int i = 0, len = number.length(); i < len; i++) {
int index = number.charAt(i) - '0';
if (buckets[index] == null) {
buckets[index] = new ArrayList<>();
}
buckets[index].add(i);
}
for (int i = 0; i < 10; i++) {
if (buckets[i] == null) {
continue;
}
// 1.不用替换，直接满足条件
if (buckets[i].size() >= K) {
minPrice = 0;
res.clear();
res.add(number);
break;
}
// 2.需要替换
change(i);
}
res.sort(String::compareTo));
System.out.println(minPrice);
System.out.println(res.get(0));
}
private void change(int num) {
int need = K - buckets[num].size();
if (need <= 0) {
return;
}
int leftNum = num - 1;
int rightNum = num + 1;
char[] cs = number.toCharArray();
char target = (char) (num + '0');
int price = 0;
/*
算法：从数字 num 开始向外扩散，采用贪心算法思想（代价为先），首先寻找相同的数字，然后寻找比该数字大1与小1的数字，
然后是大2与小2的的数字，以此类推，直到到达K个相同或者到达边界；
考虑字典顺序，自行模拟一下就能理解为什么这么找：
1.先从左往右找 rightNum 变为 num
2.再从右往左找 leftNum 变为 num
*/
while (need > 0) {
// 1.从左往右找 rightNum 变化为 num
if (rightNum <= 9 && buckets[rightNum] != null) {
List<Integer> indexs = buckets[rightNum];
for (int i = 0, len = indexs.size(); need > 0 && i < len; i++) {
int j = indexs.get(i);
cs[j] = target;
price += (rightNum - num);
need--;
}
}
// 2.从右往左找 leftNum 变化为 num
if (leftNum >= 0 && buckets[leftNum] != null) {
List<Integer> indexs = buckets[leftNum];
for (int len = indexs.size(), i = len - 1; need > 0 && i >= 0; i--) {
int j = indexs.get(i);
cs[j] = target;
price += (num - leftNum);
need--;
}
}
rightNum++;
leftNum--;
}
if (price < minPrice) {
minPrice = price;
res.clear();
res.add(String.valueOf(cs));
} else if (price == minPrice) {
res.add(String.valueOf(cs));
}
}
}
发表于 2020-04-09 17:54:07
回复(0)
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
scanner.nextLine();
String originPhone = scanner.nextLine();
Number[] numbers = new Number[n];
for (int i = 0; i < n; i++) {
numbers[i] = new Number(i, originPhone.charAt(i) - '0');
}
int diffCount = Integer.MAX_VALUE;
char[] finalRes = new char[n];
for (int i = 9; i >= 0; i--) {
for (int j = 0; j < n; j++) {
numbers[j].setTarget(i);
}
Arrays.sort(numbers, (o1, o2) -> {
//diff 小的在前面
if (o1.diff > o2.diff) {
return 1;
} else if (o1.diff < o2.diff) {
return -1;
}
//当diff相同时，分为origin相同或者不同
//当origin不同时，将大的origin放在前面，因为放在前面更有可能被替换
if (o1.origin > o2.origin) {
return -1;
} else if (o1.origin < o2.origin) {
return 1;
}
//当origin相同时，要考虑origin和target的关系
//如果origin>target,index小的在前面——先变index小的
//如果origin<target,index小的在后面——先变index大的
if (o1.target > o1.origin) {
return o2.index - o1.index;
} else {
return o1.index - o2.index;
}
});
int sum = 0;
char[] res = new char[n];
for (int j = 0; j < n; j++) {
//前k个变成target，后面的保持origin
if (j < k) {
sum += numbers[j].diff;
res[numbers[j].index] = (char) ('0' + numbers[j].target);
} else {
res[numbers[j].index] = (char) ('0' + numbers[j].origin);
}
}
if (sum < diffCount) {
diffCount = sum;
finalRes = res;
} else if (sum == diffCount) {
int index = 0;
while (index < n) {
if (finalRes[index] == res[index]) {
index++;
} else {
if (finalRes[index] > res[index]) {
finalRes = res;
}
break;
}
}
}
}
System.out.println(diffCount);
System.out.println(finalRes);
}
static class Number {
int index;
int origin;
int target;
int diff;
public Number(int index, int origin) {
this.index = index;
this.origin = origin;
}
public void setTarget(int target) {
this.target = target;
this.diff = Math.abs(origin - target);
}
}
}
发表于 2019-11-26 12:39:10
回复(0)
//js 的解法
while(line = readline()){
var lines = line.trim().split(" ");
var n = parseInt(lines[0]);
var k = parseInt(lines[1]);
var num = readline().trim().split("");
var sum = 0;
var val = 0;
var count = 0;
var gap = [];
var min = [];
function minC(a,i){
if(min[0]!=0&&!min[0]){
min[0] = a;
min[1] = i;
}else if(min[0] >a){
min[0] = a;
min[1] = i;
}
}
function repeat(same){
for(var i =0;i<10;i++){
for(var j = 0; j<n;j++){
if(Math.abs(num[j]-val)==i){
if(same == 0){
if(val <=9){
minC(sum,val);
sum=0;
val++;
repeat(k);
}else{
return;
}
}else{
same--;
sum += i;
}
}
}
}
}
repeat(k);
var cost = min[0];
var gap = min[1];
function order(){
var flag = 0;
for(var j = 0; j<10;j++){
for(var i = 0 ; i< n;i++){
if(k==0){
return;
}else if(Math.abs(num[i]-gap)==j){
if(num[i]>=gap){
num[i] = gap;
k--;
}else{
flag = 1;
}
}
}
if(flag==1){
for(var c = n-1; c>=0;c--){
if(k==0){
return;
}else if(Math.abs(num[c]-gap)==j){
num[c] = gap;
k--;
}
}
flag = 0;
}
}
}
order();
console.log(cost);
console.log(num.join(""));
}
var lines = line.trim().split(" ");
var n = parseInt(lines[0]);
var k = parseInt(lines[1]);
var num = readline().trim().split("");
var sum = 0;
var val = 0;
var count = 0;
var gap = [];
var min = [];
function minC(a,i){
if(min[0]!=0&&!min[0]){
min[0] = a;
min[1] = i;
}else if(min[0] >a){
min[0] = a;
min[1] = i;
}
}
function repeat(same){
for(var i =0;i<10;i++){
for(var j = 0; j<n;j++){
if(Math.abs(num[j]-val)==i){
if(same == 0){
if(val <=9){
minC(sum,val);
sum=0;
val++;
repeat(k);
}else{
return;
}
}else{
same--;
sum += i;
}
}
}
}
}
repeat(k);
var cost = min[0];
var gap = min[1];
function order(){
var flag = 0;
for(var j = 0; j<10;j++){
for(var i = 0 ; i< n;i++){
if(k==0){
return;
}else if(Math.abs(num[i]-gap)==j){
if(num[i]>=gap){
num[i] = gap;
k--;
}else{
flag = 1;
}
}
}
if(flag==1){
for(var c = n-1; c>=0;c--){
if(k==0){
return;
}else if(Math.abs(num[c]-gap)==j){
num[c] = gap;
k--;
}
}
flag = 0;
}
}
}
order();
console.log(cost);
console.log(num.join(""));
}
发表于 2019-10-17 10:30:47
回复(0)
#include <bits/stdc++.h>
using namespace std;
struct Node{
int cost, num, origin, target;
};
bool cmp(Node a, Node b){
if(a.cost != b.cost)
return a.cost < b.cost;
if(a.num < b.num)
return a.target < a.origin;
return b.target > b.origin;
}
int main(){
int n,k;
cin>>n>>k;
string s;
cin>>s;
int a[n];
for(int i=0;i<n;i++)
a[i] = int(s[i]-'0');
Node px[n], py[n];
int Min = INT_MAX, t;
int res[n];
for(int i=0;i<=9;i++){
for(int j=0;j<n;j++){
px[j].cost = abs(a[j]-i);
px[j].num = j;
px[j].target = i;
px[j].origin = a[j];
}
sort(px, px+n, cmp);
t = 0;
for(int j=0;j<k;j++)
t += px[j].cost;
if(t<Min){
Min = t;
for(int j=0;j<n;j++)
res[j] = a[j];
for(int j=0;j<k;j++)
res[px[j].num] = i;
}
}
cout<<Min<<endl;
for(int i=0;i<n;i++)
cout<<res[i];
cout<<endl;
return 0;
}
发表于 2019-10-03 21:54:58
回复(1)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.nextLine();
int n = Integer.parseInt(str.split(" ")[0]);
int k = Integer.parseInt(str.split(" ")[1]);
char[] ori = in.nextLine().toCharArray();
int[] count = new int[10];
for (char i : ori) {
count[i - '0'] ++;
}
int mod = Integer.MAX_VALUE;
char[] res = new char[n];
for (int i = 0; i < 10; ++ i) {
int tmpK = k - count[i];
if (tmpK <= 0) {
mod = 0;
res = ori;
break;
}
char[] tmpArr = new char[n];
for (int j = 0; j < n; ++ j) {
tmpArr[j] = ori[j];
}
int tmpMod = 0;
int l = i - 1;
int r = i + 1;
while (tmpK > 0) {
if (r < 10) {
for (int v = 0; v < n && tmpK > 0; v ++) {
if (tmpArr[v] - '0' == r) {
tmpMod += r - i;
tmpArr[v] = (char) ('0' + i);
tmpK--;
}
}
}
if (l >= 0) {
for (int v = n - 1; v >= 0 && tmpK > 0; -- v) {
if (tmpArr[v] - '0' == l) {
tmpMod += i - l;
tmpArr[v] = (char)('0' + i);
tmpK --;
}
}
}
l --;
r ++;
}
if (tmpMod < mod) {
mod = tmpMod;
res = tmpArr;
}
}
System.out.println(mod);
System.out.println(new String(res));
}
}
发表于 2019-08-06 14:59:15
回复(2)
1.遍历出现的原来数字中最小到最大值的区间范围，找到k个值（不相等要修改）
2.优先考虑数字减小
3.数字减小从前往后改，数字增加从后往前改
// 负数最小的二个值
// 全局最大的三个值
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <math.h>
#include <string.h>
#include <memory>
#include <map>
using namespace std;
struct Node {
string s;
int num;
};
bool cmp(const Node&a, const Node&b) {
if (a.num == b.num) {
return a.s < b.s;
} else {
return a.num < b.num;
}
}
int n, k;
vector<Node> ans;
string s;
void dfs(char c, int k) {
vector<int> cha;
map<int, int> prem, m;
for (int i = 0; i < s.size(); ++i) {
cha.push_back(abs(s[i]-c));
prem[s[i] - c]++;
}
sort(cha.begin(), cha.end());
int num = 0;
for (int i = 0; i < k; ++i) {
num += cha[i];
if (m[cha[i]] < prem[cha[i]]) {
m[cha[i]]++;
} else {
m[-cha[i]]++;
}
}
int cha_zhi = cha[k-1];
string r = s;
for (auto kv : m) {
// cout << kv.first << " " << kv.second <<endl;
//if (abs(kv.first) <= cha_zhi && kv.second > 0)
if (kv.first > 0) {
for (int i = 0; i < s.size(); ++i) {
if (s[i]-c== kv.first && kv.second > 0) {
kv.second--;
r[i] = c;
}
}
} else {
for (int i = s.size()-1; i >= 0; --i) {
if (s[i]-c== kv.first && kv.second > 0) {
kv.second--;
r[i] = c;
}
}
}
}
Node node;
node.num = num;
node.s = r;
ans.push_back(node);
}
int main() {
cin >> n >> k;
cin >> s;
vector<int> cha(n);
char min_ = '9', max_ = '0';
for (auto c : s) {
min_ = min(min_, c);
max_ = max(max_, c);
}
for (char c = min_; c <= max_; c++) {
dfs(c, k);
}
sort(ans.begin(), ans.end(), cmp);
cout << ans[0].num << endl;
cout << ans[0].s << endl;
return 0;
}
发表于 2020-08-02 18:51:08
回复(0)
def select_elegant(nums, k):
total = 2 ** 31 - 1
target = None
minV, maxV = min(nums), max(nums)
# find the target value with the smallest cost
for i in range(minV, maxV + 1):
t = [abs(v - i) for v in nums]
t.sort()
cost = sum(t[:k])
if cost < total:
total = cost
target = i
distance2idx = {}
for i, v in enumerate(nums):
d = v - target
if d in distance2idx:
distance2idx[d].append(i)
else:
distance2idx[d] = [i]
idx = []
bias = 0
while k:
if bias in distance2idx:
candidates = distance2idx[bias]
if len(candidates) >= k:
idx.extend(candidates[:k])
k = 0
else:
idx.extend(candidates)
k -= len(candidates)
if not k:
break
if bias == 0:
bias += 1
continue
if -bias in distance2idx:
candidates = distance2idx[-bias]
if len(candidates) >= k:
idx.extend(candidates[-k:])
k = 0
else:
idx.extend(candidates)
k -= len(candidates)
bias += 1
for i in idx:
nums[i] = target
return total, nums
N, K = [int(i) for i in input().split()]
nums = list(map(int, input()))
total, newNums = select_elegant(nums, K)
print(total)
print(''.join(map(str, newNums)))
发表于 2020-08-01 19:37:48
回复(0)
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
vector<int> nums (10,0);
//计算改成K个X时的最小代价
int caculateX(int X,int k){
int result=0;
//先算右边X+i改为X，再算左边X-i改为X
int i = 1;
int remind = k - nums[X];
//记录修改的数据
while(X+i<=9||X-i>=0){
if(X+i<=9){
if(nums[X+i]<remind){
result += (nums[X+i]*i);
remind -= nums[X+i];
}
else{
result += remind*i;
break;
}
}
if(X-i>=0){
if(nums[X-i]<remind){
result += (nums[X-i]*i);
remind -= nums[X-i];
}
else{
result += remind*i;
break;
}
}
i++;
}
return result;
}
bool cmp(pair<int,int>a, pair<int,int>b){
return a.second<b.second;
}
//计算修改K个X后的号码
string getTel(string s, int X, int k){
string ss = s;
vector<int> change(10,0);
int i = 1;
int remind = k - nums[X];
//记录修改的数据
while(X+i<=9||X-i>=0){
if(X+i<=9){
if(nums[X+i]<remind){
change[X+i] = nums[X+i];
remind -= nums[X+i];
}
else{
change[X+i] = remind;
break;
}
}
if(X-i>=0){
if(nums[X-i]<remind){
change[X-i] = nums[X-i];
remind -= nums[X-i];
}
else{
change[X-i] = remind;
break;
}
}
i++;
}
//从后往前改x-i->x这种需要增加变为x的
for(int i=ss.size();i>=0;i--){
char c = ss[i];
int cur = c - '0';
if(cur < X && change[cur]>0){
ss[i] = '0' + X;
change[cur]--;
}
}
//从前往后改x+i->x这种需要减小变为x的
for(int i=0;i<ss.size();i++){
char c = ss[i];
int cur = c - '0';
if(cur > X && change[cur]>0){
ss[i] = '0' + X;
change[cur]--;
}
}
return ss;
}
int main(){
int n,k;
cin>>n>>k;
string s;
cin>>s;
for(int i=0;i<n;i++){
nums[s[i]-'0']++;
}
vector<pair<int,int>> cost(10);
for(int i=0;i<10;i++){
if(nums[i]>=k){
cout<<0<<endl;
cout<<s<<endl;
return 0;
}
cost[i] = make_pair(i,caculateX(i,k));
}
sort(cost.begin(),cost.end(),cmp);
cout<<cost[0].second<<endl;
int min_num = 1;
for(int i=1;i<=9;i++){
if(cost[i].second>cost[0].second){
break;
}
else{
min_num++;
}
}
vector<string> tel;
int i = 0;
while(i<min_num){
tel.push_back(getTel(s,cost[i].first,k));
i++;
}
sort(tel.begin(),tel.end());
cout<<tel[0];
}
发表于 2020-06-02 11:29:00
回复(0)
| 24 ms | 9476K |
在修改成 i 的过程中，比 i 大的从前往后修改， 比 i 小的从后往前修改。
我个人觉得逻辑还是比较复杂的。这是修改后的代码，原代码有bug但由于测试用例太少也通过了。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
/**
* @Author: coderjjp
* @Date: 2020-05-08 10:18
* @Description: 选靓号
* @version: 1.0
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
int N = Integer.valueOf(s[0]);
int K = Integer.valueOf(s[1]);
char nums[] = br.readLine().toCharArray();//原始号码
int hash[] = new int[10];//存储每个数字有几个
for (int i = 0; i < N; i++)
hash[nums[i]-'0']++;
int cost = Integer.MAX_VALUE;//记录最小花费
HashMap<Integer, int[]> changed_nums = new HashMap<>();
//K:存储修改至哪个数字，V:存储被修改的数字及数量,即用map记录最小花费的情况有哪些
for (int i = 0; i <=9 ; i++ ){
int diff = K - hash[i];
int cur_cost = 0;
int cur_changed_num[] = new int[10];
for (int d = 1; d <=9 && diff > 0 ; d++){
if (i + d <= 9){//优先将大的修改至i
int pd = hash[i+d];
if (pd >= diff){
cur_changed_num[i+d] = diff;
diff=0;
}else {
cur_changed_num[i+d] = pd;
diff -= pd;
}
cur_cost += cur_changed_num[i+d]*d;
}
if (i - d >= 0){//再将小的修改至i
int pd = hash[i-d];
if (pd >= diff){
cur_changed_num[i-d] = diff;
diff=0;
}else {
cur_changed_num[i-d] = pd;
diff -= pd;
}
cur_cost += cur_changed_num[i-d]*d;
}
}
if (cur_cost < cost){//如果当前花费比之前的最小花费少
changed_nums.clear();//将之前的情况清空
changed_nums.put(i, cur_changed_num);//将当前情况记录下来
cost = cur_cost;
}
if (cur_cost == cost)//如果当前花费与之前的最小花费相同
changed_nums.put(i, cur_changed_num);
//如果当前花费比之前的最小花费少，直接跳过即可
}
System.out.println(cost);
String ans = Character.toString((char)('9'+1));
for (int c: changed_nums.keySet()) {
String cur_ans = getGMN(nums, N, c, changed_nums.get(c));
if (cur_ans.compareTo(ans) < 0)
ans = cur_ans;
}
System.out.println(ans);
}
private static String getGMN(char[] nums, int N, int c, int[] changed_num){
StringBuilder sb = new StringBuilder();
for (char cs : nums)
sb.append(cs);
for (int i = 0; i < N; i++){
if (nums[i]-'0' > c && changed_num[nums[i]-'0'] > 0){//比i大的从前往后修改
changed_num[nums[i]-'0']--;
sb.setCharAt(i, (char)('0'+c));
}
}
for (int i = N-1; i >= 0; i--){//比i小的从后往前修改
if (nums[i]-'0' < c && changed_num[nums[i]-'0'] > 0){
changed_num[nums[i]-'0']--;
sb.setCharAt(i, (char)('0'+c));
}
}
return sb.toString();
}
}
编辑于 2020-05-08 14:36:23
回复(0)
python 可以写得很明了
N, K = map(int, input().split())
nums = list(map(int, [i for i in input()])) # N长的手机号
cost = float('inf')
same_number, res = "#", [i for i in nums]
# --alg begiin-- #
for i in range(9): # 选出最优代价和即将相同的数字
gaps = [(j, abs(nums[j]-i)) for j in range(N)] # (原数字的index，该位修改后的代价)
gaps.sort(key=lambda x: x[1]) # 按代价排序
gaps = gaps[0:K] # 取最小的K个代价
sums = sum([j[1] for j in gaps]) # 代价总和
if sums < cost: # 优先数字小的 i->0~9
same_number = i
cost = sums
selection = [(j, abs(nums[j]-same_number)) for j in range(N)]
selection.sort(key=lambda x: x[1]) # 按代价排序
balance_value = selection[K-1][1] # 临界代价(对于临界代价的位要进行变大变小的判断)
selection = list(filter(lambda x:x[1]<=balance_value, selection)) # 筛选出可以更换的数字及序号
# 代价相同的情况下，若修改后变小，优先改高位，否则改低位
cnt = 0
for i, c in selection:
if c == balance_value and nums[i] < same_number: # 即将变大，先标记，暂不更改
res[i] = "b"
else:
res[i] = same_number if cnt<K else nums[i]
cnt += 1
for i in range(N-1, -1, -1): # 后从往前选变大的直到完成，顺便把变小
if res[i] == "b":
res[i] = same_number if cnt<K else nums[i]
cnt +=1
print('%d\n%s' % (cost, ''.join(map(str, res))))
编辑于 2020-04-26 02:31:58
回复(0)
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
String str = sc.next();
int[] num = new int[10];
char[] arr = new char[n];
for (int i = 0; i < n; i++) {
int index = str.charAt(i) - '0';
num[index]++;
arr[i] = str.charAt(i);
}
int[] cost = new int[10];
String[] lists = new String[10];
boolean f = false;
for (int i = 0; i < 10; i++) {
if (num[i] == 0)
continue;
if (num[i] >= k) {
System.out.println(0);
System.out.println(str);
f = true;
break;
} else {
int need = k - num[i];
int index = 1;
char[] arr1;
arr1 = Arrays.copyOf(arr, n);
while (index < 10) {
int pre = i - index;
int lat = i + index;
if (lat<=9) {
if (num[lat] >= need) {
cost[i] = cost[i] + index * need;
for (int j = 0; j < n; j++) {
if (arr1[j]-'0'==lat) {
if (need-- <= 0)
break;
arr1[j] = (char)(i+48);
}
}
lists[i] = new String(arr1);
break;
} else {
cost[i] = cost[i] + index * num[lat];
need -= num[lat];
for (int j = 0; j < n; j++) {
if ((arr1[j]-'0')==lat) {
arr1[j] = (char)(i+48);
}
}
}
}
if (pre>=0) {
if (num[pre] >= need) {
cost[i] = cost[i] + index * need;
for (int j = n-1; j >= 0; j--) {
if (arr1[j]-'0'==pre) {
if (need-- <= 0)
break;
arr1[j] = (char)(i+48);
}
}
lists[i] = new String(arr1);
break;
} else {
cost[i] = cost[i] + index * num[pre];
need -= num[pre];
for (int j = n-1; j >= 0; j--) {
if (arr1[j]-'0'==pre) {
arr1[j] = (char)(i+48);
}
}
}
}
index++;
}
}
}
if (!f) {
String res = null;
int min = Integer.MAX_VALUE;
for (int i = 0; i < 10; i++) {
if (cost[i] > 0 && min > cost[i]) {
min = cost[i];
res = lists[i];
} else if (cost[i] > 0 && min == cost[i]) {
res = res.compareTo(lists[i]) < 0 ? res : lists[i];
}
}
System.out.println(min);
System.out.println(res);
}
}
}
发表于 2020-04-16 10:11:00
回复(0)
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
using namespace std;
pair<int,string> sub_a_number(const string &number, int destine, int M ) {
// number : source phone number
// destine : destine continuous number char
// M: M continuous number char
// e.g. number = 787585, destine = 0, M = 5
// expected results is 777577
// there are only 10 cases to transfer a char to destine char
// e.g. shift 5&nbs***bsp;9 to 7 stores in data[2];
// data[i] store a pair,
// first element is distance between destine char and current char,
// second element is current char location for future used
vector<vector<pair<int, int>>> data(10);
for (int i = 0; i < number.size(); ++i) {
int current = number[i] - '0';
int delt = destine - current ;
data[abs(delt)].push_back( make_pair(delt, i) );
}
// our first aim is least cost
// thus front elements of data[i] with counts less than M
// should all be transferred
int used = 0;
int i = 0;
string result = number;
int counts = 0;
for (; i < 10; ++i) {
if (used + data[i].size() < M) {
used += data[i].size();
for (int j = 0; j < data[i].size(); ++j) {
counts += i;
result[data[i][j].second] += data[i][j].first;
}
}
else
break;
}
// for same data[i], the transferred cost are the same.
// for last data[i] that can not be totally transferred,
// we should consider the smallest dictionary key
// thus we first consider converting destine + 1 ( delt = -1 )
// then destine - 1 (delt = 1 )
int remain = M - used;
map<int, vector<int>> lap;
for (int k = 0; k < data[i].size(); ++k)
lap[data[i][k].first].push_back( data[i][k].second );
for (const pair<int, vector<int>>& item : lap) {
vector<int>& f = lap[item.first];
// for case destine + 1: we convert from left to right
// for cast destine - 1 : we convert from right to left
if (item.first < 0)
sort(f.begin(), f.end());
else
sort(f.rbegin(), f.rend());
for (int i = 0; i < f.size() && remain > 0; ++i, --remain) {
result[f[i]] += item.first;
counts += abs( item.first );
}
}
return make_pair( counts, result );
}
int main() {
int N, M;
string number;
while (cin >> N >> M >> number)
break;
int maxcost = 10000000;
string maxkey(N,'9');
for (int i = 0; i < 10; ++i) {
pair<int,string> tmp = sub_a_number(number, i, M);
if (maxcost > tmp.first) {
maxkey = tmp.second;
maxcost = tmp.first;
}
}
std::cout << maxcost << endl;
std::cout << maxkey << endl;
return 0;
}
编辑于 2020-04-10 10:14:30
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-12 12:07:54
-
2023-03-11 15:23:18
-
2023-03-07 15:54:27
-
2023-02-10 14:38:59 -
2022-11-26 19:20:03
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
