P8431 题解
liangbowen
2022-07-11 10:51:29
## 前言
[题目传送门！](https://www.luogu.com.cn/problem/P8431)
[更好的阅读体验？](https://www.luogu.com.cn/blog/liangbowen/solution-p8431)
这题题解都写得特别复杂，蒟蒻看不懂。因此，我补一篇简单的贪心题解。
## 思路
题目等同于求最小的 $p$ 使得 $f(p)>n$，则 $(p-1)$ 就是答案。
若 $f(p) > n$，首先要保证 $p$ 的位数大于等于 $n$ 的位数。根据贪心思想，我们**让末尾不存在** $0$。
保证了 $p$ 的末尾数不为 $0$，可以得到：$f(f(p)) = p$。
因此，我们可以贪心地枚举 $f(p)$。我们枚举 $1 \le i \le len(p)$，其中 $len(p)$ 表示 $p$ 的位数。
如何构造 $g = f(p)$ 呢？步骤如下。
+ 对于每个 $i$，让第 $i$ 位的数加一，自然进位。
+ 第 $[i+1, len(p)-1]$ 位均变为 $0$。
+ 第 $len(p)$ 位变为 $1$，因为末尾不可以是 $0$。
显而易见，这样构造出的数 $g$ 必定大于 $n$，并且反转后相对来说比较小，因为反转后靠近首位的 $0$ 较多。
因此，我们直接取 $(\min\limits_{i=1}^{len(n)}{g} - 1)$ 就是答案了。
听起来有些晦涩难懂，代码实现实际比较简单。
总时间复杂度 $O\Big(T \times len(n)\Big)$。
## 代码实现
```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
int LEN(LL n) //计算 n 的位数。
{
int cnt = 0;
while (n) cnt++, n /= 10;
return cnt;
}
LL f(LL n) //如题的 f(x) 函数。
{
LL ans = 0;
while (n) ans = ans * 10 + (n % 10), n /= 10;
return ans;
}
void solve()
{
LL n, minn = 9e18;
scanf("%lld", &n);
int len = LEN(n);
for (int i = 0; i <= len; i++)
{
LL p = pow(10, (LL)i); //第 i 位加一。
LL ni = n - (n % p) + p; //后面的位全部变成 0。
if (ni % 10 == 0) ni++; // 最后一位变成 1。
minn = min(minn, f(ni));
//printf("ni = %lld;\n", f(ni));
}
printf("%lld\n", minn - 1);
}
int main()
{
int T;
scanf("%d", &T);
while (T--) solve();
return 0;
}
```
希望能帮助到大家！