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

SuyctidohanQ · 2025-06-17 15:35:24 · 题解

思路分析

我的做法可能有些复杂了。

题目让我们要找一个不小于 n 的整数 m，让 m 的数位和最小，数位和相同时选数值最小的。

首先就可以写出一个拆位的函数：

LL ds(LL x) {
    LL sum = 0;
    while(x > 0) {
        sum += x % 10;
        x /= 10;
    }
    return sum;
}

先算 n 的数位和作为初始最小，为了方便处理再把 n 转成字符串，按位处理：从第一位到最后一位，每次取当前位之前的部分作为前缀，若前缀非空且最后一位是 9 就跳过，否则给前缀最后一位加 1，后面补 0 生成新数 c。

如果 c 不小于 n，就算它的数位和，比当前最小小或者相等但 c 更小，就更新最优解。

代码实现

这里给出 C++ 和 Python 的实现代码。

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

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)

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