P8431 题解

liangbowen · 2022-07-11 10:51:29 · 题解

前言

题目传送门！

更好的阅读体验？

这题题解都写得特别复杂，蒟蒻看不懂。因此，我补一篇简单的贪心题解。

思路

题目等同于求最小的 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)。

代码实现

#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;
}

希望能帮助到大家！