专栏文章

题解：P12870 [蓝桥杯 2025 国 Python A] 铺设能源管道

SSuyctidohanQ
P12870题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mip2riuq
此快照首次捕获于
2025/12/03 05:13
3 个月前
此快照最后确认于
2025/12/03 05:13
3 个月前
查看原文

思路分析

我的做法可能有些复杂了。
题目让我们要找一个不小于 nn 的整数 mm，让 mm 的数位和最小，数位和相同时选数值最小的。
首先就可以写出一个拆位的函数：
CPP
LL ds(LL x) {
	LL sum = 0;
	while(x > 0) {
		sum += x % 10;
		x /= 10;
	}
	return sum;
}
先算 nn 的数位和作为初始最小，为了方便处理再把 nn 转成字符串，按位处理：从第一位到最后一位，每次取当前位之前的部分作为前缀，若前缀非空且最后一位是 99 就跳过，否则给前缀最后一位加 11，后面补 00 生成新数 cc。
如果 cc 不小于 nn，就算它的数位和，比当前最小小或者相等但 cc 更小，就更新最优解。

代码实现

这里给出 C++ 和 Python 的实现代码。
CPP
#include<bits/stdc++.h>
#define please return 
#define AC 0
#define rep(i, a, b) for(long long i = a; i <= b; i++)
#define repr(i, a, b) for(long long i = a; i >= b; i--)

using namespace std;

typedef long long LL;

int read() {int  sum = 0, f = 1; char ch; ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9') { sum = sum * 10 + ch - '0'; ch = getchar();} return sum * f;}
void print(int x) { if(x < 0) { putchar('-'); x = -x;} if(x > 9) print(x / 10); putchar(x % 10 + '0'); return ;}

long long ds(long long x) {
    long long s = 0;
    while (x > 0) {
        s += x % 10;
        x /= 10;
    }
    return s;
}
signed main() {
	LL n; scanf("%lld", &n);
	LL ms = ds(n), bs = n;
	string sn = to_string(n);
	LL l = sn.size();
	rep(i, 0, l - 1) {
		string p = sn.substr(0, i);
		if(!p.empty() && p.back() == '9') continue;
		if(!p.empty()) p.back()++;
		else p = '1';
		string s(l - i, '0');
		LL c = stoll(p + s);
		if(c < n) continue;
		LL cs = ds(c);
		if(cs < ms || (cs == ms && c < bs)) {
			ms = cs;
			bs = c;
		}
	}
	printf("%lld\n", bs);
	please AC; 
}
PYTHON
def ds(x):
	s = 0
	while x > 0:
		s += x % 10
		x //= 10
	return s

n = int(input())
ms = ds(n)
bs = n
sn = str(n)
l = len(sn)

for i in range(l):
	p = sn[:i]
	if p and p[-1] == '9':
		continue
	if p:
		p = p[:-1] + chr(ord(p[-1]) + 1)
	else:
		p = "1"
	s = '0' * (l - i)
	c = int(p + s)
	if c < n:
		continue
	cs = ds(c)
	if cs < ms or (cs == ms and c < bs):
		ms = cs
		bs = c

print(bs)
最后，建议升橙，模拟和贪心再结合这道题目的难度已经达到了橙题的水平。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...