题目思路:二分答案

二分答案地算一下这个最大值最小可以是多少。接着直接模拟地构造就行。

C++ 二分版本 (from 2333)

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

题目内容

给定一个由字符 '0' 和 '1' 组成的字符串，代表每个位置上的两种不同类型。你需要为每个位置分配一个小写字母作为标记，规定同一个字母只能分配给类型完全相同的位置——即某个字母一旦用于 '0' 的位置，就不能出现在任何 '1' 的位置上，反之亦然。

在所有分配方案中，你希望让出现次数最多的那个字母的出现次数尽可能小。请找出并输出一个达到该最小值要求的分配方案。如果有多个合法方案，输出任意一个即可。

字符串的长度不超过 $2 \times 10^5$。

输入描述

输入只有一行，包含一个由字符 '0' 和 '1' 组成的字符串 $s$，长度不超过 $2 \times 10^5$，表示每个位置对应的类型。

输出描述

输出一行，一个长度与 $s$ 相同且仅由小写字母构成的字符串，表示一种满足要求的标记分配方案。

样例1

输入

01 01 01

输出

abcdef

说明

字符串由字符 '0' 和 '1 ' 组成，包含 3 个 '0' 和 3 个 '1 '（每个 '1 ' 包含一个空格），有效颜色字符共 6 个。由于字母表共有 26 个小写字母，每个位置都可以单独分配一个不同字母，因此出现次数最多的字母出现次数的最小值为 $1$。一种可行的构造方案是将第一个 '0' 标为 'a'，第一个 '1' 标为 'b'，第二个 '0' 标为 'c'，第二个 '1' 标为 'd'，第三个 '0' 标为 'e'，第三个 '1' 标为 'f'，得到 'abcdef'。

样例2

输入

000000000000000000000000000000

输出

aabbccddeeffgghhiijjkkllmmnnoo

说明

字符串由 30 个 '0' 组成，没有 '1'。若将最大出现次数设为 $1$，则需要 $30$ 个字母，超过了字母表容量 $26$，不可行。设最大出现次数为 $2$，则至少需要 $\lceil 30/2 \rceil = 15$ 个字母，在 $26$ 以内，因此最小最大频数为 $2$。按照每两个 '0' 分配一个新字母的方式构造：前两个 '0' 用 'a'，接下来两个用 'b'，依此类推，30 个 '0' 恰好用完 'a' 到 'o' 共 15 个字母，每个字母恰好出现 2 次，得到 'aabbccddeeffgghhiijjkkllmmnnoo'。

样例3

输入

000000000000000000001 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

输出

aabbccddeeffgghhiijjkkllmmnnooppqqrrsstt

说明

字符串由字符 '0' 和 '1 ' 组成，其中有 20 个 '0' 和 20 个 '1 '（每个 '1 ' 包含一个空格），有效颜色字符总计 40 个。

• 若最大频数为 $1$，需要 $40$ 个字母，不可行；
• 若最大频数为 $2$，则需要 $\lceil 20/2 \rceil + \lceil 20/2 \rceil = 10 + 10 = 20$ 个字母，$20 \le 26$，可行。因此最小最大频数为 $2$。

构造时，前 20 个 '0' 每两个换一个字母，依次使用 'a' 到 'j'；随后的 20 个 '1' 同样每两个换一个字母，依次使用 'k' 到 't'。最终每个字母恰好出现 2 次，输出为 'aabbccddeeffgghhiijjkkllmmnnooppqqrrsstt'。