题解 P6723 【[COCI2015-2016#5] ZAMKA】

Eason_AC2 · 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;
}