题解 | #E 小红的字符串重排#

对于字符串重排问题，有解的情况当且仅当所有元素的出现次数不超过总元素个数的一半，因此首先记录每个元素的出现次数判断是否输出”-1“

int n(s.size());
std::map<char, int> m;
for (char c : s)
{
	++m[c];
	if (m[c] > n / 2)
	{
		std::cout << -1 << std::endl;
		return;
	}
}

然后关于元素如何重排，可以考虑贪心的策略，即遍历每个位置，将所有未排元素按剩余数量从大到小排序，在每个位置放下的元素为【出现次数最多且与原元素不同】的元素

// 将map中的数据拷贝到vector中，便于排序
std::vector<std::pair<char, int>> alphas(m.begin(), m.end());

std::string ans;
for (int i(0); i < n; ++i)
{
	std::sort(alphas.begin(), alphas.end(),
	[](std::pair<char, int> a, std::pair<char, int> b)
	{
		return a.second > b.second;
	});
	for (std::pair<char, int>& ci : alphas)
	{
		if (ci.first != s[i] && ci.second)
		{
			ans += ci.first;
			--ci.second;
			break;
		}
	}
}

然而这种贪心策略并不一定能得到答案
比如数据：aabbc
按照上述方式将输出：aabb
没错，只输出四个字母，因为当遍历到第五个位置时，未放置的元素只剩一个‘c’，且与原元素相同，因此该位置有空缺（比赛的时候没想到这种情况，只拿了210分）

然后我想到一种改进方法，上面提到，当所有元素的出现次数都不超过总个数一半时，必定有解
因此可以考虑,当上述贪心策略在某个位置无法正确放置元素时，可从已放置过的位置遍历，寻找一个元素与其换位，使得两个位置都能满足条件

std::string ans;
for (int i(0); i < n; ++i)
{
	std::sort(alphas.begin(), alphas.end(),
	[](std::pair<char, int> a, std::pair<char, int> b)
	{
		return a.second > b.second;
	});
	/*新增*/
  	bool find(false);
	for (std::pair<char, int>& ci : alphas)
	{
		if (ci.first != s[i] && ci.second)
		{
			ans += ci.first;
			--ci.second;
			/*新增*/
          	find = true;
			break;
		}
	}
	/*新增*/
  	if (!find)
	{
		for (int j(0); j < ans.size(); ++j)
		{
			if (ans[j] != s[i] && s[j] != s[i])
			{
				ans += ans[j];
				ans[j] = s[i];
				break;
			}
		}
	}
}

经过置换之后便可得到符合要求的重排字符串
完整代码附上

void solve(void)
{
    std::string s;
	std::cin >> s;
	int n(s.size());
	std::map<char, int> m;
	for (char c : s)
	{
		++m[c];
		if (m[c] > n / 2)
		{
			std::cout << -1 << std::endl;
			return;
		}
	}
	std::vector<std::pair<char, int>> alphas(m.begin(), m.end());
	std::string ans;
	for (int i(0); i < n; ++i)
	{
		std::sort(alphas.begin(), alphas.end(),
		[](std::pair<char, int> a, std::pair<char, int> b)
		{
			return a.second > b.second;
		});
		bool find(false);
		for (std::pair<char, int>& ci : alphas)
		{
			if (ci.first != s[i] && ci.second)
			{
				ans += ci.first;
				--ci.second;
				find = true;
				break;
			}
		}
		if (!find)
		{
			for (int j(0); j < ans.size(); ++j)
			{
				if (ans[j] != s[i] && s[j] != s[i])
				{
					ans += ans[j];
					ans[j] = s[i];
					break;
				}
			}
		}
	}
	std::cout << ans << std::endl;
}