hihocoder1327 分隔相同字符贪心

#include <bits/stdc++.h>
#define ll long long
#define maxn 100100
using namespace std;
char s[maxn];
int a[300];
int check(char ch){
    if(a[ch] == 0) return 0;
    int sum = 0, ma = 0;
    for(int i=‘a‘;i<=‘z‘;i++){
        sum += a[i];
        ma = max(ma, i==ch?(a[i]-1):a[i]);
    }
    if(2*ma>sum) return 0;
    else return 1;
}
int main(){
    int l, num=1;
    scanf("%s", s);
    l = strlen(s);
    memset(a, 0, sizeof(a));
    for(int i=0;i<l;i++) a[s[i]]++;
    s[0] = ‘.‘;
    while(1){
        int i;
        for(i=‘a‘;i<=‘z‘;i++){
            if(check(i)&&(i!=s[num-1])){
                a[i]--;
                s[num++] = i;
                break;
            }
        }
        if(i>‘z‘) break;
    }
    if(num-1 == l) printf("%s\n", s+1);
    else printf("INVALID\n");
    //main();
    return 0;
}