Hướng dẫn giải của [CSES 1743] String Reorder

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Đầu tiên ta hãy phân tích khi nào có thể xây dựng một xâu sao cho không có hai ký tự kề nhau nào giống nhau. Số lần xuất hiện tối đa của một ký tự đạt được khi nó xuất hiện ở mọi vị trí cách đều nhau, bao gồm cả vị trí đầu tiên và cuối cùng. Điều này dẫn đến bất đẳng thức ~2k\le n+1~, trong đó ~k~ là số lần xuất hiện của ký tự xuất hiện nhiều nhất và ~n~ là độ dài xâu. Việc xây dựng là khả thi khi và chỉ khi bất đẳng thức trên được thỏa mãn.

Bây giờ, ta có thể xây dựng đáp án từng ký tự một. Để có xâu có thứ tự từ điển nhỏ nhất, tại mỗi bước ta sẽ chọn ký tự nhỏ nhất một cách tham lam. Điều kiện trên được dùng để kiểm tra xem xâu có thể được hoàn thành bằng cách chọn một ký tự cụ thể hay không.

#include <iostream>
using namespace std;

int count[128];

int main() {
    string s;
    cin >> s;

    int n = s.size();

    for (auto c : s) {
        count[(int)c]++;
    }

    auto check = [&](int length) {
        for (int i = 'A'; i <= 'Z'; ++i) {
            if (count[i] * 2 > length + 1) {
                return false;
            }
        }
        return true;
    };

    if (!check(n)) {
        cout << -1 << '\n';
        return 0;
    }

    char prev = '$';
    for (int i = 1; i <= n; ++i) {
        for (int nxt = 'A'; nxt <= 'Z'; ++nxt) {
            if (!count[nxt]) continue;
            if (nxt == prev) continue;
            count[nxt]--;
            if (check(n - i)) {
                cout << (char)nxt;
                prev = nxt;
                break;
            }
            count[nxt]++;
        }
    }
    cout << '\n';
}

Chương trình tham khảo

#include <iostream>
using namespace std;

int count[128];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;

    int n = s.size();

    for (auto c : s) {
        count[(int)c]++;
    }

    auto check = [&](int length) {
        for (int i = 'A'; i <= 'Z'; ++i) {
            if (count[i] * 2 > length + 1) {
                return false;
            }
        }
        return true;
    };

    if (!check(n)) {
        cout << -1 << '\n';
        return 0;
    }

    char prev = '$';
    for (int i = 1; i <= n; ++i) {
        for (int nxt = 'A'; nxt <= 'Z'; ++nxt) {
            if (!count[nxt]) continue;
            if (nxt == prev) continue;
            count[nxt]--;
            if (check(n - i)) {
                cout << (char)nxt;
                prev = nxt;
                break;
            }
            count[nxt]++;
        }
    }
    cout << '\n';
}

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.