CF118C. Fancy Number题解

发表于 分类于

题目传送门

题意：有一个 nn 位的数字串，每位为 0−90-9。每次操作可以更改一位的数字，代价为新旧两位数字之差。问使字符串存在某一个数的出现次数超过 kk 的最小代价。如果有多种方案，输出字典序最小的。

求最小代价非常简单，枚举要让哪个数出现超过 kk 次，然后将所有位求出将这一位改成该数的代价，排个序前 kk 小值即可。难点在于如何让字典序最小。

做法一

考虑排序时不仅要求代价从小到大，对于同样代价的两位，要么是原来比较大，减小为要求的数，要么是原来比较小，增大为要求的数，此时优先改数字大的那位，因为改完可以变小，字典序一定减小。如果两位相同，考虑是增大还是减小，如果减小则越靠前越好，如果增大则越靠后越好。

By cxm1024

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
#include<bits/stdc++.h>
using namespace std;
signed main() {
    int n,k,ans=1e9;
    string s,t;
    cin>>n>>k>>s;
    for(char i='0';i<='9';i++) {
        vector<pair<int,int> > dis;
        for(int j=0;j<s.size();j++)
            dis.push_back({abs(s[j]-i),j});
        sort(dis.begin(),dis.end(),[&](pair<int,int> p,pair<int,int> q) {
            if(p.first!=q.first) return p.first<q.first;
            if(s[p.second]!=s[q.second]) return s[p.second]>s[q.second];
            if(s[p.second]>i) return p.second<q.second;
            else return p.second>q.second;
        });
        int res=0;
        string tmp=s;
        for(int j=0;j<k;j++)
            res+=dis[j].first,tmp[dis[j].second]=i;
        if(res<ans||(res==ans&&tmp<t))
            ans=res,t=tmp;
    }
    cout<<ans<<endl<<t<<endl;
    return 0;
}

做法二

考虑小于最大花费的一定全选，所以字典序只在等于最大花费的位之间有影响。对于等于最大花费的位，只需要先正着处理比要变成的数大的，再反着处理比它小的（原因同做法一），避免了复杂的比较函数。

By tomekkulczynski

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
char s[11013], tmp[11013];

int main()
{
    int n,k;
    scanf("%d %d %s",&n,&k,s);
    int ret = 9 * n + 1;
    string w = "";
    REP(c, 10) {
        VI t;
        REP(i, n) t.PB(abs(s[i] - '0' - c));
        sort(ALL(t));
        int  ss = 0;
        REP(i, k) ss += t[i];
        if(ss < ret) ret = ss, w = "a";
        if(ss == ret) {
            REP(i, n+1) tmp[i] = s[i];
            int d = t[k-1], ww = 0;
            REP(i, n) if(abs(s[i] - '0' - c) < d) tmp[i] = c + '0', ww++;
            REP(i, n) if(ww < k && s[i] == c + '0' + d) tmp[i] = c + '0', ww++;
            FORD(i, n-1, 0) if(ww < k && s[i] == c + '0' - d) tmp[i] = c+'0', ww++;
            w = min(w, (string)tmp);
        }
    }
    printf("%d\n%s\n",ret, w.c_str());
    return 0;
}

做法三

考虑从每位花费的角度枚举。由于一定是先选花费小的，再选花费大的，于是从小到大枚举花费，对于这个花费，有可能是变小的花费，也有可能是变大的花费，此时先正着处理变小，再反着处理变大，直至取足数量即可。

By watashi

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
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n, k, m, s;
    string pat, tmp;
    pair<int, string> ans = make_pair(1000000007, "");

    cin >> n >> k;
    cin >> pat;
    for (int d = 0; d < 10; ++d) {
        s = 0;
        tmp = pat;
        m = count(tmp.begin(), tmp.end(), '0' + d);
        for (int x = 1; x < 10; ++x) {
            if (d + x < 10) {
                char y = '0' + (d + x);
                for (int i = 0; m < k && i < n; ++i) {
                    if (tmp[i] == y) {
                        tmp[i] = '0' + d;
                        s += x;
                        ++m;
                    }
                }
            }
            if (0 <= d - x) {
                char y = '0' + (d - x);
                for (int i = n - 1; m < k && i >= 0; --i) {
                    if (tmp[i] == y) {
                        tmp[i] = '0' + d;
                        s += x;
                        ++m;
                    }
                }
            }
        }
        ans = min(ans, make_pair(s, tmp));
    }
    cout << ans.first << endl << ans.second << endl;

    return 0;
}

做法四

可以使用类似搜索的思路来递归计算。原理类似做法三，每次扩张一格距离，依次处理，使用递归来简化代码。每次判断当前小还是大，递归时跳到对面处理，直到取足数量。

By Komaki

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
using namespace std;
#define li       	long long int
#define rep(i,to)	for(li i=0;i<((li)(to));++i)
#define pb       	push_back
#define sz(v)    	((li)(v).size())
#define bit(n)   	(1ll<<(li)(n))

li get(char c){
    return c-'0';
}
string str;
li cal(li rem,li to,li now){
    li res=0;
    if(to<now){
        if(now<=9){
            for(li i=0;i<sz(str);i++)if(get(str[i])==now){
                str[i]=to+'0';
                rem--;
                res+=abs(now-to);
                if(rem==0) return res;
            }
        }
        res+=cal(rem,to,to-(now-to));
    }else if(now<to){
        if(0<=now){
            for(li i=sz(str)-1;0<=i;i--)if(get(str[i])==now){
                str[i]=to+'0';
                rem--;
                res+=abs(now-to);
                if(rem==0) return res;
            }
        }
        res+=cal(rem,to,to+(to-now)+1);
    }else{
        rep(i,sz(str))if(get(str[i])==now) rem--;
        if(rem<=0) return res;
        res+=cal(rem,to,to+1);
    }
    return res;
}

int main(){
    li n,k;
    string base;
    cin>>n>>k>>base;
    li best=bit(60);
    string ans="";
    rep(i,10){
        str=base;
        li tmp=cal(k,i,i);
        if(tmp<best || (tmp==best && str<ans)){
            best=tmp;
            ans=str;
        }
    }
    cout<<best<<endl;
    cout<<ans<<enddl;
}