原题
题目大意： 字符串 S 由小写英文字母组成，判断是否可以重排 S 使相邻字符都不同。若可以则给出一种方案。
这里我是想了一个插空构造。设按字符数从大到小排，字符依次为 \(c0, c1, c2, ...\)。
首先把 \(c0\) 放进空串 \(S'\) 里，形成 \(|c0| - 1\) 个空隙。如果剩下的字符不够每一个空隙都能有一个字符插入，即 \(|c0| - 1 > |S| - |c0|\)，那么显然不合法。
接下来将 \(c1\) 从左往右尽可能插入一个字符到 \(c0\) 的空隙中，如果够则在 \(S'\) 末尾插一个（类似奇偶交错）。\(|c0| \ge |c1|\)，所以 \(c1\) 必然能够插完。这个时候 \(c1\) 也被隔开了。
如果 \(|c0| = |c1|\)，那么刚好插完所有空隙（和末尾），那么回到 \(S'\) 开头开始下一轮，再按这种奇偶交错方法插入 \(c2\)。反之，则在之后插入 \(c2\) 直到完毕再开始下一轮。
这个时候需要考虑，假如第二种情况再回到 \(S'\) 开头后，剩余 \(c2\) 的个数足够一直插入到上一轮开始插入 \(c2\) 的位置怎么办。可以证明不会有这种情况：
上一轮开始插入 \(c2\) 的位置前有 \(|c1| \cdot 2 + 1\) 个字符，形成 \(|c1| \cdot 2\) 个可插入 \(c2\) 的空隙。这远远大于 \(|c2|\)，所以不可能。
按照这种方法就可以证明不合法的充要条件是\(|c0| - 1 > |S| - |c0|\) 并给出一种构造了。其实从第二轮开始可以从 \(S'\) 开头之前开始插入，不过这样已经可以了。
#include<iostream>
#include<algorithm>
using namespace std;
int T;
struct node {int cnt,let;
}
ch[26];
bool cmp(node x, node y) {return x.cnt > y.cnt;
}
int main() {cin >> T;while (T--) {string s;cin >> s;for (int i = 0; i < 26; i++) ch[i] = {0,'a' + i};for (char i: s) ch[i - 'a'].cnt++;sort(ch, ch + 26, cmp);if (ch[0].cnt - 1 > s.size() - ch[0].cnt) { // 判断是否合法cout << "No" << endl;continue;}cout << "Yes" << endl;int tot = -1;for (int i = 25; i >= 0; i--) // 统计出现字符种类数if (ch[i].cnt) {tot = i;break;}string ans = "";ans.append(ch[0].cnt, ch[0].let); // 先放入 c0ch[0].cnt = 0;bool stop = 0;int flag = 1; // 标记当前还有剩余的最多的一种字符while (!stop) {string tmp = ""; // 直接模拟插入不太好写，故维护插入空隙的字符所形成的子序列while (tmp.size() < ans.size()) { // 最多插入原串长度个字符，不然插不下if (ch[flag].cnt == 0) flag++; // 用完就换下一种字符插入if (flag > tot) { // 没有字符了，停止插入stop = 1;break;}if (tmp.size() + ch[flag].cnt <= ans.size()) { // 可以在这一轮把 ch[flag] 插完tmp.append(ch[flag].cnt, ch[flag].let);ch[flag].cnt = 0;} else { // 否则ch[flag].cnt -= ans.size() - tmp.size(); // 注意这一句要先写，不然 tmp.size() 会变tmp.append(ans.size() - tmp.size(), ch[flag].let);}}string ttmp = "";for (int i = 0; i < tmp.size(); i++) ttmp += ans[i], ttmp += tmp[i]; // 形成一轮插入后的字符串ttmp.append(ans.substr(tmp.size())); // 如果中途没有字符，tmp.size()会小一些，故把原串剩下的直接接到后面。// 显然这一句只可能在最后一轮执行。由合法条件易得假如第二轮执行这一句，// 原串最多只会剩一个字符，故没有问题。ans = ttmp;}cout << ans << endl;}return 0;
}