解题思路
给定只含小写字母的字符串 s（长度为 n），定义“中位符”为：将字符按字典序（从小到大）排序后，取第 ceil(n/2) 个字符（从 1 开始计数）。
直接排序可做，但更高效的方法是利用字母表只有 26 个字符这一事实，使用计数排序（桶计数）：
- 统计 26 个小写字母在字符串中的出现次数
cnt[0..25]。
- 计算目标排名
k = (n + 1) // 2（即 ceil(n/2)）。
- 从
a 到 z 依次累加出现次数，第一次使前缀和 >= k 的字母即为答案。
P3798.第1题-字符串的中位符
题目内容
给定一个长度为 n 仅由小写字组成的字符串 "s"，请输出它的中位符。
定义一个字符串的”中位符”为将该字符串按字典序(从小到大)排序后第 [2n]个字符(字符从 1 开始计数);
字符的字典序即其对应的 ASCII 码 (a<⋅⋅⋅<z)。
在这里，[x] 代表对 z 进行上取整操作。
输入描述
输入包含两行:
第一行输入一个整数 n(1≦n≦2×105) ，表示字符串长度;
第二行输入长度为 n 的字符串 "s"，仅由小写字母组成。
输出描述
输出一个字符，表示字符串"s"的中位符。
样例1
输入
3
cba
输出
b
