A104223.午枫的数字分离 贪心

看到排序后分割得a、b，求a*b的最大值，我有一个直觉：把n中的数字抽出，按从大到小排序，设当前序列中最大数为c，把c放到a、b中较小数的末尾。
该如何证明呢？
易得先放大的数，再放小的数。
设上述步骤的一共用k步，假设前k-1步选择最优。
在第k步，有a k-1 <= b k-1，剩余最大数字m。
令x = a k-1，y = b k-1。
若把m放在x末尾，则x' = 10x + m
若把m放在y末尾，则y' = 10y + m
设积s1 = x' * y = 10xy + my , 积s2 = y' * x = 10xy + mx。
s1 - s2 = 10xy + my - (10xy + mx) = m(y - x)
因为x <= y ，所以(y - x) >= 0
又因为m >= 0 ，所以m(y - x) >= 0
即s1 >= s2
可得在第k步时把剩余最大数字给a、b中较小数更优。
在第k-1步，该结论仍然成立......
通过归纳法可证明上述方法的正确性。
代码附下

#include <iostream>
using namespace std;
const int L = 10; 
int num[L + 5]; //序列储存n的每一位数字 
int main()
{
	string n; cin >> n;
	for (char c : n)
		++num[c - '0'];
	int a = 0 , b = 0;
	for (int i = 9 ; i >= 0 ; --i)
	{
		for (int j = 1 ; j <= num[i] ; ++j)
		{
			int c = i; //当前最大数 
			if (a <= b) a = a * 10 + c;
			else b = b * 10 + c;
		}
	}
	cout << a * b << endl;
	return 0;
}

时间复杂度O(1)
空间复杂度O(1)
最开始时a = b = 0 。
最终a和b会各得到n中1个不为0的数作为最高位，不会出现有前导零的情况。