Word Processor

题意

给定 N 个单词和每行字符上限 K。

需要按顺序输出这些单词，使每一行的非空格字符数不超过 K。如果下一个单词放入当前行会超过 K，就把它放到下一行。

同一行单词之间用一个空格分隔，行末不能有多余空格。

思路

朴素模拟

可以先把每一行的单词保存下来，最后统一输出：

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/**
 * 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-07-11 14:24
 * update_at: 2026-07-11 14:25
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, k;
string word[MAXN]; // 第 i 个单词
vector<string> lines[MAXN];
int line_cnt;

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

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> word[i];
    }

    line_cnt = 1;
    int current_len = 0;

    // 朴素模拟：先把单词放进每一行的数组里，最后统一输出。
    for (int i = 1; i <= n; i++) {
        int len = (int)word[i].size();
        if (current_len + len > k) {
            line_cnt++;
            current_len = 0;
        }

        lines[line_cnt].push_back(word[i]);
        current_len += len;
    }

    for (int i = 1; i <= line_cnt; i++) {
        for (int j = 0; j < (int)lines[i].size(); j++) {
            if (j > 0) {
                cout << ' ';
            }
            cout << lines[i][j];
        }
        cout << '\n';
    }

    return 0;
}

这个写法非常直观：每个单词要么加入当前行，要么新开一行。

边扫描边输出

正式代码可以不保存所有行，只维护一个变量：

text

1current_len = 当前行已有的非空格字符数量

对每个单词 w：

如果 current_len + len(w) > K，先输出换行，再输出 w；
否则把 w 放在当前行，如果当前行已有单词，就在它前面输出一个空格。

注意空格不计入 current_len，所以更新长度时只加单词长度。

代码

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/**
 * 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-07-11 14:24
 * update_at: 2026-07-11 14:25
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, k;
string word[MAXN]; // 第 i 个单词

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

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> word[i];
    }

    int current_len = 0; // 当前行已有的非空格字符数量

    for (int i = 1; i <= n; i++) {
        int len = (int)word[i].size();

        if (current_len + len > k) {
            cout << '\n' << word[i];
            current_len = len;
        } else {
            if (current_len > 0) {
                cout << ' ';
            }
            cout << word[i];
            current_len += len;
        }
    }
    cout << '\n';

    return 0;
}

复杂度

每个单词处理一次，时间复杂度为 $O(N)$ 。

保存单词数组，空间复杂度为 $O(N)$ 。

总结

这题的关键是分清“输出时需要空格”和“判断长度时不统计空格”。

只要维护当前行已有多少个非空格字符，就能直接模拟题目规则。

目录

题意

思路

朴素模拟

边扫描边输出

代码

复杂度

总结