【題解】Codeforces 1296E2. String Coloring (hard version)

【題目敘述】http://codeforces.com/contest/1296/problem/E2

#include <iostream>
using namespace std;
 
int n, a[26], ans[200005], cnt;
string s;
 
int main() {
    cin >> n;
    cin >> s;
    for (int i = 0; i < 26; i++){
        a[i] = 'a';
    }
    for (int i = 0; i < n; i++){
        for (int j = 0; j < 26; j++){
            if (s[i] >= a[j]){
                a[j] = s[i];
                ans[i] = j;
                cnt = max(cnt, j);
                break;
            }
        }
    }
    cout << cnt+1 << "\n";
    for (int i = 0; i < n; i++){
        cout << ans[i]+1 << " ";
    }
    cout << "\n";
}
分享本文 Share with friends