Java教程

P8431 题解

本文主要是介绍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)\)。

代码实现

#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

这篇关于P8431 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!