C - Magical Rearrangement

2021江苏省赛JSCPC

给出数字0 ~ 9每一个的个数，用完所给的全部数字组成一个任意两个相邻数字都不相等的最小的数字字符串。

3
0 0 1 0 0 0 0 0 0 2
2 0 1 0 0 1 0 2 0 0
3 0 1 0 0 0 0 0 0 0

929
205707
-1

贪心,分类讨论。话说，贪心可真不容易，而且这题好多细节。

• 从高位开始贪，每次选择一个使接下来有解的最小的数字。
• 假设选取第 i 个数字作为当前所选的最优情况
  设：剩余的数字中数量最多的数字 j 的数量为 max；其他数字的数量为 rest。
  以下两种情况都是无解的情况。
  { i = j max >= rest + 1 i ≠ j max > rest + 1 begin{cases} i = j& text {max >= rest + 1}\ i neq j & text{max > rest + 1} end{cases} {i=ji​=j​max >= rest + 1max > rest + 1​
• 判断数据是否有解
  由于首位数字不是0，所以下面的代码solve函数中就不再需要特殊判断数量最多的数字是不是0了。但开始的时候需要特判一下，判断数字0是不是最多的数字。（max，与text与上面的略不一样，只是初始的情况下判断是否有解，不需要选取数字）
  { m a x ⩾ r e s t + 1 数字0是最多的 m a x > r e s t + 1 其他情况 begin{cases} max geqslant rest + 1& text {数字0是最多的}\ max > rest + 1 & text{其他情况} end{cases} {max⩾rest+1max>rest+1​数字0是最多的其他情况​

int num[10];

int solve(int last)
{
	//假设选取第i个数字，如果选后剩下的情况
	for (int i = 0; i <= 9; i++)
	{
		if (num[i] == 0 || i == last) continue;

		num[i]--;//假设选i
		int idx = 0, rest = 0;
		for (int j = 0; j <= 9; j++)
		{
			rest += num[j];
			if (num[j] > num[idx])
				idx = j;
		}
		rest -= num[idx];
		
		if (idx == i && num[idx] >= rest + 1 ||
			idx != i && num[idx] > rest + 1)
			num[i]++;
		else return i;
	}

	return -1;
}

int main()
{
	IOS;
	int T; cin >> T;
	while (T--)
	{
		int maxn = 0, rest = 0, flag;//判断数量最多的数字是否为0
		for (int i = 0; i <= 9; i++)
		{
			cin >> num[i];

			if (num[i] > maxn)
			{
				maxn = num[i];
				if (i == 0) flag = 1;
				else flag = 0;
			}

			rest += num[i];
		}
		rest -= maxn;

		if (rest == 0 && num[0] == 1)
		{
			cout << 0 << endl;
			continue;
		}

		if (flag)//0的数量最多
		{
			if (maxn >=  rest + 1)
			{
				cout << -1 << endl;
				continue;
			}
		}
		else
		{
			if (maxn > rest + 1)
			{
				cout << -1 << endl;
				continue;
			}
		}
		
		int x = solve(0);//问题的主要难点
		while (x >= 0)
		{
			cout << x;
			x = solve(x);
		}
		cout << endl;
	}

	return 0;
}