一道很好的构造题。简单来说，给你一个序列 $\{b\}$，$b_i$ 表示 $a_i$ 各位数字之和，请还原出序列 $\{a\}$。有两个附加条件，一是序列 $\{a\}$ 单增，二是 $\{a\}$ 尽可能的小。
对于第二个条件，很容易想到要贪心求解。倘若没有第一个条件，那么显然 $b_i = 9a+b(0<b<9)$ 的形式是最优的，即还原出的数形如 $b99\cdots9$。那么有第一个条件时，不难想到根据 $b_{i - 1}$ 与 $b_i$ 的大小进行分类讨论。
先从 $b_{i - 1} < b_i$ 这种简单的情况看起。相较于前一个数，只需要把多的部分 $b_i - b_{i - 1}$ 按照贪心的思想去填入即可。举个栗子，如果 $a_{i - 1} = 129$，多出了 $8$ 需要填，那么在 $2$ 上加上 $7$ 补成最大的上限 $9$，然后将剩余的 $8 - 7 = 1$ 填入 $1$，最后变成了 $299$。
再来看 $b_{i - 1} \ge b_i$ 的情况。从低位往高位找到第一个不是 $9$ 的位置，尝试将该位加 $1$，往高位的方向均不变，往低位的方向重新排列。这里需要注意是否合法（也就是剩余数字之和在减去那些已经确定的数后是否大于等于 $0$）。当然，往低位的方向的排列方式直接按照贪心的思路即可。若位数不够，则需要补 $0$，这也是为什么之前判断合法时只需要满足大于等于 $0$ 即可。如果全部遍历完也未出现可以填的，那么只能新开一位并填上 $1$，然后剩下的按照贪心的思路即可。
在编写代码的时候，分类三种构造的函数。第一种是无条件限制，直接贪心填入。第二种是弱依赖，即需要补充多的部分的第一种情况。第三种便是需要较大改动的第二种情况，其中按照贪心进行填入的部分直接调用第一个函数即可。
完整代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int n,a[MAX];
string ans[MAX];
string easy_make (int x);
string medium_make (string la,int x);
string hard_make (string la,int x);
int main ()
{
n = read ();
for (int i = 1;i <= n;++i) a[i] = read ();
for (int i = 1;i <= n;++i)
{
if (i == 1) ans[i] = easy_make (a[i]);
else if (a[i] > a[i - 1]) ans[i] = medium_make (ans[i - 1],a[i]);
else ans[i] = hard_make (ans[i - 1],a[i]);
}
for (int i = 1;i <= n;++i) cout<<ans[i]<<endl;
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
string easy_make (int x)
{
string s = "";
for (int i = 1;i <= x / 9;++i) s += '9';
x %= 9;
if (x) s = char (x + 48) + s;
return s;
}
string medium_make (string la,int x)
{
int len = la.size ();int sum = x;
string s = "";
for (int i = 0;i < len;++i) sum -= la[i] - '0';
for (int i = len - 1;~i;--i)
{
if (!sum) s = la[i] + s;
else s = char (la[i] + min (9 - (la[i] - '0'),sum)) + s,sum -= min (9 - (la[i] - '0'),sum);
}
return easy_make (sum) + s;
}
string hard_make (string la,int x)
{
int len = la.size ();
for (int i = len - 1;~i;--i)
{
if (la[i] != '9')
{
string s = "";int sum = 0;
for (int j = 0;j < i;++j) s += la[j],sum += la[j] - '0';
s += char (la[i] + 1);sum += la[i] - '0' + 1;
if (x - sum < 0) continue;
string nw = easy_make (x - sum);
int p = len - s.size () - nw.size ();
for (int j = 1;j <= p;++j) s += '0';
return s + nw;
}
}
string s = "1";++len;
string nw = easy_make (x - 1);
int p = len - s.size () - nw.size ();
for (int i = 1;i <= p;++i) s += '0';
return s + nw;
}
|
