题目传送门!
更好的阅读体验?
这题题解都写得特别复杂,蒟蒻看不懂。因此,我补一篇简单的贪心题解。
题目等同于求最小的 \(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)\) 呢?步骤如下。
显而易见,这样构造出的数 \(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; }
希望能帮助到大家!
首发:2022-07-11 10:51:29