Chuyển số độ dài N chứa ít nhất K lần một chữ số trong C++

Cho số độ dài N. Chuyển đổi các chữ số sao cho có ít nhất một chữ số xuất hiện ≥ K lần. Chi phí = tổng giá trị tuyệt đối thay đổi. Tìm chi phí nhỏ nhất và số kết quả.

Chương trình C++

#include <bits/stdc++.h> 
using namespace std; 

int get_final(int n, int k, string a) {
    int modtemp, co;
    string temp;
    pair<int, string> ans = make_pair(INT_MAX, "");
    
    for (int i = 0; i < 10; i++) {  // Thử mỗi chữ số mục tiêu 0-9
        temp = a;
        modtemp = 0;
        co = count(a.begin(), a.end(), i + '0');
        
        for (int j = 1; j < 10; j++) {  // Khoảng cách thay đổi
            if (i + j < 10) {  // Tăng chữ số
                for (int p = 0; p < n; p++) {
                    if (co >= k) break;
                    if (i + '0' == temp[p] - j) {
                        temp[p] = i + '0';
                        modtemp += j;
                        co++;
                    }
                }
            }
            if (i - j >= 0) {  // Giảm chữ số
                for (int p = n - 1; p >= 0; p--) {
                    if (co >= k) break;
                    if (i + '0' == temp[p] + j) {
                        temp[p] = i + '0';
                        modtemp += j;
                        co++;
                    }
                }
            }
        }
        ans = min(ans, make_pair(modtemp, temp));
    }
    cout << ans.first << endl << ans.second << endl;
}

int main() {
    int n = 5, k = 4;
    string a = "21122";
    get_final(n, k, a);
    return 0;
}

Kết quả

1
21222

Giải thích

• Số gốc: 21122
• Mục tiêu: có 1 chữ số xuất hiện ≥ 4 lần
• Chuyển thành 21222 (chữ số 2 xuất hiện 4 lần)
• Chi phí: |2-1| = 1 (chỉ thay đổi 1 chữ số)