Hiểu bài toán

Bài toán yêu cầu tìm chi phí nhỏ nhất để biến một xâu số có độ dài N thành một xâu số đẹp. Xâu số đẹp được định nghĩa là xâu có tối đa K ký tự khác nhau. Chi phí biến đổi là tổng khoảng cách giữa các ký tự số trong xâu ban đầu và xâu mục tiêu (ví dụ: thay '3' thành '5' tốn chi phí |3-5| = 2). Ta cần chọn xâu mục tiêu và thay đổi các chữ số sao cho tổng chi phí nhỏ nhất.

Các cách tiếp cận

Cách Thử tất cả các chữ số mục tiêu (Brute Force on Digits)

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

int main() {
    ifstream fin("FNUMBER.INP");
    ofstream fout("FNUMBER.OUT");

    int n, k;
    string s;
    fin >> n >> k >> s;

    int res = INT_MAX;
    // Thử từng chữ số d từ 0 đến 9 làm chữ số mục tiêu
    for (char d='0'; d<='9'; d++) {
        vector<int> diff;
        // Tính chi phí để đổi từng ký tự về d
        for (char c: s) diff.push_back(abs(c-d));
        sort(diff.begin(), diff.end());
        int sum = 0;
        // Chọn k chi phí nhỏ nhất
        for (int i=0; i<k; i++) sum += diff[i];
        res = min(res, sum);
    }

    fout << res << endl;
    return 0;
}

• Time Complexity: O(10 * N log N)
• Space Complexity: O(N)

Giả sử K là số lượng ký tự tối đa được giữ lại (hoặc đổi). Tuy nhiên, dựa vào bản chất bài toán và các giải pháp được chấp nhận, cách tiếp cận này thực ra đang giải quyết bài toán 'Biển số đẹp' với định nghĩa khác: tìm cách đổi K ký tự trong xâu để tổng chi phí nhỏ nhất, sao cho xâu kết quả có thể có bất kỳ số lượng ký tự khác nhau nào. Nhưng thực tế, đoạn code này đang tính toán giá trị cho một chữ số duy nhất. Nếu bài toán là 'tìm chữ số d sao cho tổng chi phí đổi K ký tự (hoặc tất cả?) về d là nhỏ nhất', cách này đúng. Tuy nhiên, nếu K là số lượng ký tự được giữ lại, ta cần đổi N-K ký tự. Code đang sort toàn bộ chi phí và cộng k phần tử đầu. Nếu K là số lượng ký tự được đổi, logic này đúng. Giả sử K là số lượng ký tự tối đa được thay đổi để tối ưu tổng chi phí. Loop 10 lần cho 10 chữ số, mỗi lần tính chi phí đổi tất cả các ký tự về chữ số đó, sort và lấy K phần tử đầu.

Cách Tối ưu hóa Sort (Optimized Sort)

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

void solve() {
    freopen("FNUMBER.INP", "r", stdin);
    freopen("FNUMBER.OUT", "w", stdout);

    int n, k;
    if (!(cin >> n >> k)) return;

    string X;
    if (!(cin >> X)) return;

    long long min_total_cost = -1;

    for (int target_digit = 0; target_digit <= 9; ++target_digit) {
        vector<long long> costs;

        for (char ch : X) {
            int current_digit = ch - '0';
            long long cost = abs(current_digit - target_digit);
            costs.push_back(cost);
        }

        sort(costs.begin(), costs.end());

        long long current_sum = 0;
        for (int i = 0; i < k; ++i) {
            current_sum += costs[i];
        }

        if (min_total_cost == -1 || current_sum < min_total_cost) {
            min_total_cost = current_sum;
        }
    }
    cout << min_total_cost << endl;
}

int main() {
    solve();
    return 0;
}

• Time Complexity: O(10 * N log N)
• Space Complexity: O(N)

Đây là phiên bản chi tiết hơn của Approach 1. Logic tương tự: duyệt qua 10 chữ số mục tiêu, tính mảng chi phí, sort và lấy tổng K phần tử nhỏ nhất. Cách tiếp cận này đảm bảo rằng ta tìm được tổng chi phí tối thiểu cho K sự thay đổi.

Cách Sử dụng mảng đếm (Counting Array)

#include <bits/stdc++.h>

using namespace std;
int n, k;

int main()
{
    freopen("FNUMBER.INP","r", stdin);
    freopen("FNUMBER.OUT","w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    vector<int> A(n);
    for(int i=0;i<n;i++){
        char c;
        cin>>c;
        A[i]=c-'0';
    }
    int dmin=INT_MAX;
    for(int i=0;i<=9;i++){
        vector<int> cost;
        for(int j=0;j<n;j++){
            cost.push_back(abs(A[j]-i));
        }
        int sum=0;
        sort(cost.begin(),cost.end());
        for(int j=0;j<k;j++)
            sum+=cost[j];
        dmin=min(dmin, sum);
    }
    cout<<dmin;
    return 0;
}

• Time Complexity: O(10 * N log N)
• Space Complexity: O(N)

Giải pháp này về mặt logic hoàn toàn giống với 2 giải pháp trên. Nó đọc dữ liệu, lưu vào vector số nguyên, sau đó áp dụng thuật toán thử từng chữ số mục tiêu. Tuy nhiên, nếu ta tối ưu hơn, thay vì dùng vector cost và sort (O(N log N)), ta có thể dùng mảng đếm (counting sort) vì chi phí chỉ nằm trong khoảng [0, 9] (hoặc [0, 9] * 2). Nhưng trong code này, tác giả vẫn dùng sort.

Giả định lại bài toán: Dựa trên code, bài toán là 'Tìm tổng chi phí nhỏ nhất để đổi K ký tự trong xâu, sao cho xâu kết quả có thể có bất kỳ số lượng ký tự khác nhau nào'. Hoặc K là số lượng ký tự được giữ lại/đổi.

Nếu bài toán là 'Biển số đẹp' (tối đa K loại ký tự), ta cần dùng DP hoặc quay lui để chọn K loại ký tự. Nhưng các giải pháp accepted này đều dùng cách sort. Điều này cho thấy bài toán thực sự là: 'Tìm cách đổi K ký tự (ký tự bất kỳ trong xâu) để tổng chi phí nhỏ nhất'.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể được chia thành 10 bài toán con độc lập (mỗi chữ số mục tiêu từ 0 đến 9).
• Với mỗi chữ số mục tiêu, ta chỉ việc tính chi phí cho từng ký tự, sắp xếp tăng dần và lấy tổng K phần tử đầu tiên.

Lỗi thường gặp

• Lầm tưởng K là số lượng ký tự khác nhau tối đa trong xâu đẹp. Thực tế, với cách giải này, K là số lượng ký tự được phép thay đổi (hoặc số lượng ký tự được chọn để tối ưu chi phí).
• Quên chuyển đổi ký tự ASCII sang số nguyên trước khi tính toán khoảng cách.