自动搬运

查看原文

来自洛谷，原作者为

	Eason_AC2 ...

搬运于2025-08-24 22:23:22，当前版本为作者最后更新于2020-08-04 07:39:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Content

给定三个数 $L,D,X$ ，求在 $[L,D]$ 内各数位的和恰好为 $X$ 的最小数 $N$ 和最大数 $M$ （保证 $N,M$ 一定存在）。

数据范围：$1\leqslant L \leqslant D \leqslant 10^4,1 \leqslant x \leqslant 36$。

Solution

很简单的一道模拟题。

先预处理出 $1$ 到 $10^4$ 的各数位之和，然后先从左往右遍历，第一个找到的数即为最小的满足要求的数。在从右往左遍历，第一个找到的数即为最大的满足要求的数（证明无需多讲）。

主要是先预处理这里降低一下复杂度，其他的都没什么好讲的。

Code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;

int sum[10007];

int main() {
	for(int i = 1; i <= 10000; ++i) {
		int p = i;
		while(p) {
			sum[i] += p % 10;
			p /= 10;
		}
	}
	int l, d, x;
	scanf("%d%d%d", &l, &d, &x);
	for(int i = l; i <= d; ++i) {
		if(sum[i] == x) {
			printf("%d\n", i);
			break;
		}
	}
	for(int i = d; i >= l; --i) {
		if(sum[i] == x) {
			printf("%d\n", i);
			break;
		}
	}
	return 0;
}