题解 AT4161 【[ARC099B] Snuke Numbers】
皎月半洒花
2020-03-04 22:02:52
首先这个是可以猜出一部分结论的，大概就是考虑如果数字里面 $9$ 比较多的话肯定会比较符合，因为这样 $\rm S$ 值就会显然更大。其次也是可以打表的。
但是这个题本质上不存在规律。所以以上两种方式可能会挂的很惨。
考虑一种可行的构造方式。首先知道，$1$ 一定是可行的。对于每个当前的 $x$ ，选择那个使得 $y>x$ 且 $\frac{y}{\rm S(y)}$ 最小的 $y$ 来替代当前的 $x$ 。不难理解这样做是可行的。
那大概考虑如何去证明第一个性质，或者稍微形式化一点：
> 假设 $y$ 是 $>x$ 且 $\frac{y}{\rm S(y)}$ 最小的那个 $y$，且假设从高位到低位，$x$ 和 $y$ 第一次出现不同的地方是**从低到高的** 第 $p$ 位，那么会有 $y$ 的从低到高 $1\sim p$ 位均为 $9$ 。
证明时考虑如下：
1、对于 $1\sim p-1$ 位的证明是不难的。考虑假设 $y$ 不符合上述规则，那么设出一个 $y'$ ，其中 $1\sim p-1$ 均是 $9$ ，且 $y'$ 的第 $p$ 位是 $y$ 的第 $p$ 位 $-1$ 的数值。那么可以知道 $x\leq y'<y$ 且 $\mathrm{S}(y')\geq \mathrm S(y)$ 。这样的话 $\frac{y}{\mathrm S(y)}>\frac{y'}{\mathrm S(y')}$ 与 $y$ 的定义矛盾。所以 $1\sim p-1$ 均为 $9$。
2、再考虑第 $p$ 位。设 $y$ 的第 $p$ 位值为 $s$，设 $y'=y-10^{p-1}\cdot s$ ，那么有
$$
\frac{y}{\mathrm S(y)}=\frac{y'+10^{p-1}s}{\mathrm S(y')+s}
$$
那么考虑此时 $y'$ 不变，等式右边是一个凹函数(先不考虑怎么凹)，在 $s=9$ 或者 $s=0$ 时取得最值。根据定义可知此处应该选择 $s=9$ （因为 $y$ 的第 $p$ 位至少要比 $x$ 的第 $p$ 位大 $1$）
_______
综上，可知后缀必然是某些 $999...999$ 的形式。从个位数向上推就好了。复杂度在 $\Omega(n)\sim O(n\log n)$ 左右。
```cpp
int n ;
long long ans ;
long long base = 1 ;
double s(long long x){
int ret = 0 ; long long y = x ;
while (x) ret += (x % 10ll), x /= 10ll ;
return (1.0 * y) / (1.0 * ret) ;
}
int main(){
cin >> n ;
while (n --){
while (1){
if (s(ans + base) > s(ans + base * 10ll))
base *= 10ll ; else break ;
}
ans += base ;
printf("%lld\n", ans) ;
}
}
```