题目传送门
「HGOI-1」Number
题目背景
$\text{bh1234666}$ 正在学习乘法！
题目描述
$\text{bh1234666}$ 有一定数量的数字 $0 \sim 9$，现在他想让你寻找一种分配方案，将它们分成两个整数，使得他们的乘积 $p$ 最大。
由于 $\text{bh1234666}$ 不喜欢太大的数，所以你只需要输出两个非负整数，使它们的乘积等于最大乘积 $p$，但是这两个整数 $0 \sim 9$ 的数量不能等于给定的数量（任意一个数字数量不相等即可，不考虑前导零）。
$\text{bh1234666}$ 是很善良的，如果 $0 \sim 9$ 的数量等于给定的数量了，你依旧可以得到的一半的分。
输入格式
第一行十个整数 $c_0,c_1,\cdots c_9$，分别表示 $0 \sim 9$ 的个数。
输出格式
共两行每行一个非负整数，分别表示你给出的两个非负整数。
样例 #1
样例输入 #1
1 2 3 2 1 1 2 1 2 1样例输出 #1
13949030
620572547提示
样例解释
最大可能乘积为 $97643210 \times 88653221=13949030 \times 620572547=8656385075279410$。
若输出 $97643210 \times 88653221$ 则只能得到一半的分，因为 $0\sim 9$ 出现的次数与给定的相同。
数据范围及约定
本题采用捆绑测试，共有 $5$ 个subtask，最终分数为所有subtask分数之和。
$$ \def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \textbf{Score} & \sum c_i\le \cr\hline 1 & 10 & 20 \cr\hline 2 & 20 & 100 \cr\hline 3 & 20 & 5000 \cr\hline 4 & 20 & 10^6 \cr\hline 5 & 30 & 10^7 \cr\hline \end{array} $$
对于 $100\%$ 的数据，保证 $1 \le c_i$，$\sum c_i \le 10^7$。
说明
本题有spj，两数乘积正确得一半的分，数量与给出的不同且乘积正确得全部分数。故每一subtask的得分为其中所有数据点得分的最小值。
题解
第一部分：证明何时乘积最大
已知：$a+b=k(k为常数)$
求证：当$|a-b|$最小时，$a\times b$最大
证明：
设：
$$a+b=x \tag{1}$$
$$a-b=y \tag{2}$$
$(1)+(2)$得：
$$2a=x+y \tag{3}$$
$(1)-(2)$得：
$$2b=x-y \tag{4}$$
$(3)\times(4)$得：
$$\begin{aligned}4ab&=(x+y)(x-y)\\&=x^2-y^2\end{aligned}$$
$\therefore y^2$越小$ab$越大
即：$|a-b|$越小，$ab$越大。
第二部分：构造数列
第一点毋庸置疑的是，$a$和$b$的数字由高位到低位数字是非单调递增的。这样$a,b$两个相同数位上的两个数字是确定的了，那么这两个数的和也就是确定的了，问题就在于这两个数字分别是放在$a$还是$b$上。
由上一部分的证明可得，为了使两个数字乘积最大，就要使两个数字的差值尽可能小，由此，存在一种构造法：
- 将数字从大到小放置，并假设每个数都有原数据数量，每次放置两个数，分别放置在$a,b$的第$i$位上（从低位到高位。
- 如果将要放置的两个数相等，毋庸置疑，$a,b$的第$i$位都是这同一个数。
当然，可能会存在要放置的两个数不相等（某个数字能用的个数只剩下一个，需要用下一个数字补充）这里需要分成两种情况判断：
- 这里假设$a \gt b$，如果是第一次遇到这种情况，那么就把大的数字放在$a$的下一位，小的数字放在$b$的下一位。
- 如果是第二次遇到这种情况，就把小的数字放在$a$的下一位，大的数字放在$b$的下一位，即相反处理。
如此，就可以使得$a-b$的值最小，得到那一半分情况下的正确答案。
第三部分：重构数列
为了拿到满分成绩，需要对这个数列重构，使得存在一个数字的个数与样例所给不同。
观察上述数列：可以发现$a,b$中必有一个数字末尾数字为$0$（$c_i>1$），即这个数字一定能被$2$整除，$a,b$数字的首位数字非$8$即$9$，那么这个数字乘$2$之后一定是进一位的，因为进了一位，而另个数字位数一定不变，数字总量多了一位，所以一定符合满分的条件。
实现方法很简单，构造时使用每一个数组位置存储一个数字的方法，最后使用高精度算法处理即可。
代码
#include<bits/stdc++.h>
using namespace std;
namespace Fast{...}
using namespace Fast;
int num[10],a[M],b[M],nowa,nowb,cnt;
bool p;
int main(){
for(int i=0;i<=9;i++){
read(num[i]);
cnt+=num[i];
}
for(int i=9;i>=0;i--){
int cnt=num[i]/2;
for(int j=1;j<=cnt;j++){
a[++nowa]=i;
}
for(int j=1;j<=cnt;j++){
b[++nowb]=i;
}
if(p&&num[i]%2&&i!=0){
a[++nowa]=i-1;
b[++nowb]=i;
num[i-1]--;
}
if(!p&&num[i]%2&&i!=0){
a[++nowa]=i;
b[++nowb]=i-1;
num[i-1]--;
p=1;
}
if(p&&num[i]%2&&i==0){
b[++nowb]=i;
}
if(!p&&num[i]%2&&i==0){
a[++nowa]=i;
}
}
if(a[nowa]==0){
for(int i=1;i<=nowa;i++){
if(a[i]%2==1)
a[i+1]+=10;
a[i]/=2;
print(a[i]);
}
for(int i=nowb;i>=0;i--){
b[i]*=2;
b[i]+=b[i+1]/10;
b[i+1]%=10;
}
enter;
int outp=0;
if(b[0]!=1)
outp=1;
for(int i=outp;i<=nowb;i++){
print(b[i]);
}
}
else{
for(int i=1;i<=nowb;i++){
if(b[i]%2==1)
b[i+1]+=10;
b[i]/=2;
print(b[i]);
}
for(int i=nowa;i>=0;i--){
a[i]*=2;
a[i]+=a[i+1]/10;
a[i+1]%=10;
}
enter;
int outp=0;
if(a[0]!=1)
outp=1;
for(int i=outp;i<=nowa;i++){
print(a[i]);
}
}
return 0;
}
