Number

题目描述

给出一个 $k$ 位十进制整数 $n$ ，对它进行按位四舍五入：从最低位开始向前依次操作当前数从右数第 $j$ 位——该位数字 $\leqslant 4$ 就把它及其右侧所有位全部置 $0$ ； $\geqslant 5$ 同样置 $0$ ，但向左一位进 $1$ ，进位按十进制连锁传播，最高位进位可使位数增加（位数编号规则不变）。共执行 $k-1$ 次操作（ $k=1$ 时无操作）。每组数据第一行是位数 $k$ ，第二行是 $n$ （共 $T$ 组）；输出从原数开始共 $k$ 个数，用 " -> " 连接。

输入样例：第一行 3 表示 3 组数据，三组依次为 k=4, n=2023、k=1, n=9、k=3, n=197。输出样例：2023 -> 2020 -> 2000 -> 2000、9、197 -> 200 -> 200（每组一行）。数据范围： $1 \leqslant T \leqslant 10$ ， $1 \leqslant k \leqslant 100$ 。

思路

每一步就是把"当前数"舍入到 $10^j$ 的倍数（从右数第 $j$ 位 $\geqslant 5$ 就进位）： $n$ 最多 100 位装不进整数，用字符串读入、逆序存进数组（个位在 0 号位）模拟。关键在两点：低位进位会改写高位数字，所以每步必须看当前数而不是原始数（如 14995 最低位进位后千位 4 变 5，之后还要再进位）；某位达到 10 要用 while 连锁向高位进位并预留位数增加的空间（如 299997 -> 300000、95 -> 100）。每步判断与置 0 是 $O(1)$ ，进位链最多 $O(k)$ ，总复杂度 $O(k^2)$ 。

参考代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-28 19:08
 * update_at: 2026-08-28 19:08
 */
// A. Number：按位四舍五入的数组模拟。
// 逆序存数字（a[0] 是个位），每步对"当前数"的第 p 位判断：
// 该位 >= 5 就向前一位进 1 并连锁进位，然后把第 p 位及以下全部置 0。
#include <bits/stdc++.h>
using namespace std;

const int MAXK = 105;

int k;
int a[MAXK + 5]; // a[0] 是个位，逆序存放数字，多留几个位置给最高位进位

// 输出当前数：从最高非零位开始，跳过前导零。
void print_num() {
    int top = MAXK + 4;
    while (top > 0 && a[top] == 0) top--;
    for (int i = top; i >= 0; i--) cout << a[i];
}

void solve() {
    string s;
    cin >> k >> s;
    memset(a, 0, sizeof(a));
    for (int i = 0; i < k; i++) a[i] = s[k - 1 - i] - '0';

    print_num();
    for (int p = 0; p < k - 1; p++) { // 从个位向高位依次处理 k-1 步
        // 第 p 位 >= 5：舍去后向前一位进 1
        if (a[p] >= 5) {
            a[p + 1]++;
            // 连锁进位：某位超过 9 就继续向更高位进，直到全部小于 10
            int j = p + 1;
            while (a[j] >= 10) {
                a[j + 1] += a[j] / 10;
                a[j] %= 10;
                j++;
            }
        }
        a[p] = 0; // 舍去第 p 位（更低的位在之前步骤已全部为 0）
        cout << " -> ";
        print_num();
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

目录

题目描述

思路

参考代码