A. Line Breaks 题解

题目大意

给定 $n$ 个单词和一个长度为 $m$ 的条幅，要求连续选择前 $x$ 个单词（无间隔拼接），使得总长度不超过 $m$。求最大的合法 $x$（若第一个单词就超长，答案为 $0$）。

解题思路

这是一道纯模拟/前缀和的入门题，逻辑非常简单：

1. 依次计算前1个、前2个...前n个单词的总长度；
2. 找到最大的 $x$，满足总长度 $\le m$；
3. 若第一个单词长度就超过 $m$，直接返回 $0$。

核心逻辑

• 单词必须连续、完整放在条幅上，不能拆分；
• 直接累加长度，一旦超过 $m$ 就停止，此时的计数就是答案。

C++ 代码实现

#include <iostream>
#include <string>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        int sum = 0, ans = 0;
        for (int i = 0; i < n; ++i) {
            string s;
            cin >> s;
            sum += s.size(); // 累加单词长度
            if (sum <= m) {  // 总长度不超限，更新答案
                ans = i + 1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

代码解释

1. 输入处理：先读取测试用例数 $t$，循环处理每组数据；
2. 累加长度：遍历每个单词，累加总长度；
3. 判断合法性：如果总长度 $\le m$，说明前 $i+1$ 个单词合法，更新答案；
4. 输出结果：每组测试用例结束后输出最大的 $x$。

样例验证

以样例输入为例：

• 第一组：3 1，单词 a(1)、b(1)、c(1) → 累加1个刚好=1，答案1；
• 最后一组：3 2，第一个单词abc(3)>2 → 答案0。

完全匹配样例输出，逻辑正确。

复杂度分析

• 时间复杂度：$\mathcal{O}(t \cdot n)$，$t \le 1000, n \le 50$，完全满足时间限制；
• 空间复杂度：$\mathcal{O}(1)$，仅用了几个变量存储。