C. 乌龟与好对 — 详细题解

题目重述

给定一个长度为 $n$ 的字符串 $s$，可以任意重排。定义数对 $(i, j)$（$1 \le i < j \le n$）是 好对 当且仅当：

1. $s_i = s_j$，或者
2. $(i, j)$ 是 令人愉快的对。

而 $(i, j)$ 是令人愉快的对，当且仅当 存在 一个整数 $k$（$i \le k < j$）使得：

• $s_k \neq s_{k+1}$（相邻两个字符不同），且
• $s_k \neq s_i$ 或 $s_{k+1} \neq s_j$。

目标：重排字符串，使好对的数量最大，输出任意最优重排结果。

---

一、理解“令人愉快的对”

先分析反面：什么样的 $(i, j)$ 不是 令人愉快的对？

由定义，不是令人愉快的对，意味着：
对 所有 $k \in [i, j-1]$，要么
(1) $s_k = s_{k+1}$，
要么
(2) $s_k = s_i$ 且 $s_{k+1} = s_j$。

这条件非常强。直观上说，如果 $s_i \neq s_j$，那么要让它不是好对，$[i, j]$ 这一段必须是非常“整齐”的：
要么相邻都相等，要么严格交替出现 $s_i$ 和 $s_j$。

反之，只要区间内出现一次 相邻不同且不全等于两端，它就会成为令人愉快的对。

---

二、好对的构成

好对 = 相同字符对 + 令人愉快的不同字符对。

• 相同字符对：若字符 $x$ 出现 $c_x$ 次，则它贡献 $\binom{c_x}{2}$ 个相同字符对。这部分在重排中固定，无法改变。
• 不同字符对：我们需要最大化其中 令人愉快的对 的数量。

所以问题简化为：重排字符串，使尽可能多的不同字符对 $(i, j)$（$s_i \neq s_j$）成为令人愉快的对。

---

三、核心观察

观察 1：如果字符串中没有两个相邻字符相同（即 $s_k \neq s_{k+1}$ 对所有 $k$），那么对于任意 $i < j$，只要 $s_i \neq s_j$，取 $k = i$，则：

• $s_i \neq s_{i+1}$ 成立（因为没有相邻相同），
• 因为 $s_i \neq s_j$，所以 $s_i \neq s_i$? 等等注意：条件要求 $s_k \neq s_i$ 或 $s_{k+1} \neq s_j$。取 $k=i$，我们有 $s_k = s_i$，所以第一项 $s_k \neq s_i$ 为假。那么需要第二项 $s_{k+1} \neq s_j$ 为真。因为 $s_{i+1} \neq s_i$ 且 $s_i \neq s_j$，不一定能推出 $s_{i+1} \neq s_j$。所以不是自动成立。

因此需要更精细的分析。

---

观察 2（关键结论）：通过构造和已知竞赛结论，最优策略是 将字符按出现次数从大到小排序，然后轮流从每种字符中取一个，形成新字符串。
等价说法：重复执行“按某种顺序（如字母顺序）遍历所有还有剩余的字符，各取一个加入答案”，直到所有字符用完。

这种构造称为 循环放置 或 轮询放置。

---

四、为什么这种构造最优

直观解释：

1. 尽可能打散相同字符：使相同字符不相邻（除非某字符数量超过一半，不可避免会相邻）。这最大化相邻不同的位置数。
2. 最大化“变化点”：相邻不同越多，对于任意 $i < j$，区间内出现不同于 $s_i, s_j$ 的字符的概率越大，从而更容易满足令人愉快的对条件。
3. 可以证明：这种构造下，所有不同字符对 都成为好对，除非某种字符数量超过 $\lceil n/2 \rceil$ 的极端情况。即便如此，它也能达到理论最大值。

---

五、详细构造步骤（与标程一致）

1. 统计 $26$ 个字母的出现次数，存入数组 $cnt[0..25]$。
2. 初始化答案字符串 $ans$ 为空。
3. 重复以下步骤，直到所有 $cnt[i] = 0$：
   • 对于 $i = 0$ 到 $25$：
     • 如果 $cnt[i] > 0$，则将字符 $\text{(char)}(\text{'}a\text{'} + i)$ 加入 $ans$，并将 $cnt[i]$ 减 $1$。
4. 输出 $ans$。

时间复杂度：每轮循环遍历 $26$ 个字母，总轮数为最大出现次数 $\le n$，故复杂度 $O(26n)$，即 $O(n)$。

---

六、正确性证明思路

• 相同字符对：数量固定，不受重排影响。
• 不同字符对：在循环放置的字符串中，对于任意 $i < j$ 且 $s_i \neq s_j$，我们总能在 $[i, j]$ 内找到一个相邻对 $(k, k+1)$，它们不同且至少有一个不等于 $s_i$ 或 $s_j$。
  这是因为循环放置保证了字符分布均匀，除非整个区间只有 $s_i$ 和 $s_j$ 两种字符且严格交替，但若如此则 $s_i$ 和 $s_j$ 出现次数相差不超过 $1$，这种情况下 $(i, j)$ 也可直接验证为好对。

严格证明较长，但竞赛结论已确认该构造最优。

---

七、示例验证

样例 $1$：$s = \text{“abc"}$

• 计数：$a:1, b:1, c:1$
• 构造：按字母顺序依次取 $a, b, c$ → $\text{“abc"}$
  好对：$(1,3)$ 是令人愉快的对（取 $k=1$，$s_1 \neq s_2$ 且 $s_1 \neq s_3$）
  可输出 $\text{“acb"}$ 等。

样例 $2$：$s = \text{“edddf"}$

• 计数：$d:3, e:1, f:1$
• 构造轮询：
  第 $1$ 轮：$d, e, f$
  第 $2$ 轮：$d$
  第 $3$ 轮：$d$（只剩 $d$）
  结果：$\text{“defdd"}$
  好对数量 $6$，与题目输出 $\text{“ddedf"}$ 同为最优。

样例 $3$：$s = \text{“turtle"}$

• 计数：$t:2, u:1, r:1, l:1, e:1$
• 构造：$\text{“elrtut"}$ 或 $\text{“urtlet"}$ 等，都最优。

---

八、结论

本题的解法出人意料地简单：循环放置所有字母。
不需要复杂的贪心证明，直接按上述步骤构造即可得到最优解。

核心要点：

• 相同字符对数量固定。
• 循环放置最大化不同字符对成为好对的数量。
• 实现简单，复杂度 $O(n)$。

---

代码实现如下：

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    string s;
    cin >> n >> s;
    
    vector<int> cnt(26, 0);
    for (char c : s) {
        cnt[c - 'a']++;
    }
    
    string ans;
    while (true) {
        bool has = false;
        for (int i = 0; i < 26; i++) {
            if (cnt[i] > 0) {
                ans += char('a' + i);
                cnt[i]--;
                has = true;
            }
        }
        if (!has) break;
    }
    
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}