Codeforces Round #705 K-beautiful Strings 模拟

题意

给你一个n和k。n表示字符串长度。

定义beautiful string：如果一个串里面，所有字母出现的次数都能被k整除，这个字符串就是美的。

定义字符串大小（字符串长度都是n）：以第一个不一样的字符算，第一个不一样的字符小的串就小。

现在要找：大于或等于输入s的，最小的，美的，串。

题解

显然是贪心，但是这个贪心比较显然。更多还是细节处理和模拟……

首先如果n和k都不整除就不用看了。一定是-1。
然后对于本身就美的，也不用看了，直接输出s。
然后就开始正题了：
1. 首先，肯定是找改动点。也就是和原串第一个不一样的点。从后往前找，改动点越后面当然越好。
2. 然后，看前面缺什么，补什么就好了。

但是里面其实一万个细节

首先，改动点的选择。改动点要考虑改动后是否能填前面的坑。比如对于ddbccc和3。当考虑改b的时候，如果改成c，那么后面要填坑的是1个d和2个b。而如果b改成d，那么后面什么坑都不用填。
相关处理：

    private static int getChangePos() {
        for (int i = n - 1; i >= 1; i--) {
            int now = s[i] - 'a';
            if (now == 25) continue;

            int totalNeed = 0;
            boolean useful = false;
            for (int j = 0; j < 26; j++) {
                int need = getNeed(i - 1, j);
                totalNeed += need;
                if (need != 0 && j > now) {
                    useful = true;
                }
            }
            if (useful) totalNeed -= 1;
            else totalNeed += m - 1;

            int afterMe = n - 1 - i;
            if (totalNeed <= afterMe) {
                return i;
            }
        }
        return 0;
    }

再有在真正改改动点的时候思路其实又不一样了。因为改动点其实不一定非要填前面的坑。只要后面能填上，就越小越好。
相关处理：

            int afterMe = n - 1 - changeAtMe;

            int currentChar = s[changeAtMe] - 'a';
            int nextChar = currentChar + 1;

            int totalDirectNeed = 0;
            for (int i = 0; i < 26; i++) {
                totalDirectNeed += getNeed(changeAtMe - 1, i);
            }
            if (totalDirectNeed + m - 1 > afterMe) {
                for (int i = nextChar; i < 26; i++) {
                    if (getNeed(changeAtMe - 1, i) != 0) {
                        nextChar = i;
                        break;
                    }
                }
            }

            count[changeAtMe][currentChar]--;
            count[changeAtMe][nextChar]++;
            s[changeAtMe] = (char) (nextChar + 'a');

最后，填坑要从后面往前填。坑填完了，就全部填a。

代码

我好菜啊。。。这个题显然是个水题，但是写了好久，而且还挂了几发。。。