PTA 算法1-10~11 输出 1 ~ n

算法1-10~11 输出 1 ~ n

分数 10

作者 陈越

单位 浙江大学

给定正整数 n，输出 1 ~ n，每个数字占一行。

本题旨在测试不同的算法在各种数据情况下的表现。各组测试数据特点如下：

  • 数据 0：测试基本正确性；
  • 数据 1：n=1；
  • 数据 2：n=1000；
  • 数据 3：n=10000；
  • 数据 4：n=100000；
  • 数据 5：n=1000000。

输入格式:

输入在一行中给出正整数 n (≤106)。

输出格式:

输出 1 ~ n，每个数字占一行。

输入样例:

1
3

输出样例:

1
2
3
1
2
3

法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    // 使用'\n'代替endl，减少缓冲区刷新次数
    for (int i = 1; i <= n; i++) {
        cout << i << '\n';
    }
    // 循环结束后手动刷新一次
    cout.flush();
    return 0;
}

1.超时问题

  • 如果直接写cout << i << endl;
测试点 提示 内存(KB) 用时(ms) 结果 得分
0 sample 等价 548 2 答案正确 5 / 5
1 最小n 488 2 答案正确 1 / 1
2 n=1000 520 3 答案正确 1 / 1
3 n=10000 556 15 答案正确 1 / 1
4 n=100000 1104 132 答案正确 1 / 1
5 n=1000000 2636 400 运行超时 0 / 1
  • n = 1000000会运行超时
  • 使用’\n’代替endl，减少缓冲区刷新次数

2.性能差异说明：

  • endl = 换行 + 刷新缓冲区，每次调用都会触发 IO 操作
  • '\n' 仅换行，数据会先存到缓冲区，满了才会写入输出设备
  • 对于 100 万级别的输出，这种优化能将 IO 操作从 100 万次减少到几次，大幅提升速度

法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <stdlib.h>

int main() {
    // 设置stdout缓冲区为16KB（全缓冲模式）
    setvbuf(stdout, NULL, _IOFBF, 16384);
    
    int n;
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i++) {
        // 用"\n"代替强制刷新，配合缓冲区优化
        printf("%d\n", i);
    }
    
    // 最后手动刷新一次（确保缓冲区剩余数据输出）
    fflush(stdout);
    return 0;
}

setvbuf(stdout, NULL, _IOFBF, 16384);是另一种优化输出性能的方式，和我之前说的用'\n'代替endl并不矛盾，它们是从不同层面优化输出效率的方法。

两种方法的区别与联系：

  1. setvbuf的作用：这行代码手动设置了标准输出的缓冲区大小为 16KB（表示全缓冲模式）。效果是：printf/cout 的输出会先存满缓冲区，再一次性写入设备，减少了 IO 交互次数（默认缓冲区可能更小，比如 4KB）。
  2. '\n'代替endl的作用：避免自带的强制刷新操作，让数据自然积累到缓冲区再输出，本质是减少。
  3. 结合使用效果更好：如果你用输出，可以同时使用增大缓冲区 + 用代替（或中用），双重优化效果更佳