Moe's CF Life

喵~ 大家好呀！今天本喵要给大家带来一道超级基础又可爱的入门题解，题目是 A. Line Breaks。这道题就像是帮小猫整理毛线球一样，简单又有趣，最适合刚开始学习算法的你了喵~

题目大意

有一位叫 Kostya 的朋友，他有一些单词需要写在两条纸带上。

第一条纸带：长度是固定的，最多只能写 m 个字符。
第二条纸带：长度无限长，随便写多少都行。

Kostya 需要从他的单词列表里，按顺序选出前 x 个单词，写在第一条纸带上。剩下的所有单词就都写在第二条纸带上。单词之间没有空格，但每个单词必须完整地写在一条纸带上，不能分开。

我们的任务就是，帮 Kostya 找到一个最大的 x，使得前 x 个单词的总长度加起来，正好不超过第一条纸带的容量 m。

简单来说，就是从头开始，尽可能多地往第一条纸带里塞单词，直到塞不下为止，然后告诉 Kostya 一共塞了几个，的说。

解题方法

这道题的核心思想其实非常非常简单，就是贪心！喵呜~ 就像小猫看到小鱼干，肯定是先吃离自己最近的那个嘛！

我们的策略也是一样的：

我们准备一个计数器 words_on_first_strip 来记录放在第一条纸带上的单词数量，初始为 0。
再准备一个变量 current_length 来记录当前第一条纸带上已经用掉的长度，初始也为 0。
然后，我们从第一个单词开始，一个一个地按顺序检查。
对于每个单词，我们都试着把它“放”到第一条纸带上。在放之前，先检查一下：当前已用长度 + 这个新单词的长度 是不是会超过 m？
- 如果没超过 m：太棒了！我们成功地把这个单词放上去了。那么就把它的长度加到 current_length 上，并且把单词计数器 words_on_first_strip 加一。然后继续看下一个单词。
- 如果超过了 m：呜呜，这个单词太长了，放不下了。因为题目规定必须是连续的前 x 个单词，所以一旦这个单词放不下，它后面的所有单词也都没机会了。我们就只能停下来。

循环结束后，words_on_first_strip 里面存的数字，就是我们能放下的最大单词数啦！

举个栗子：n=4, m=12，单词是 hello, world, and, codeforces。

看 hello (长度5)。0 + 5 <= 12。可以放！当前长度 current_length = 5，单词数 words_on_first_strip = 1。
看 world (长度5)。5 + 5 <= 12。可以放！当前长度 current_length = 10，单词数 words_on_first_strip = 2。
看 and (长度3)。10 + 3 > 12。放不下啦！停！
所以最多能放 2 个单词。

是不是很简单呢，喵~？

题解代码

这是本喵写的 C++ 代码，加了一些注释方便你理解哦。

cpp

#include <iostream>
#include <string>
#include <vector>

// 这个函数是用来加速C++的输入输出的，让程序跑得更快喵~
// 在处理大量数据时很有用！
void setup_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

// 这是解决单个测试用例的函数
void solve() {
    int n; // 单词总数
    int m; // 第一条纸带的最大长度
    std::cin >> n >> m;

    int words_on_first_strip = 0; // 记录放在第一条纸带上的单词数
    int current_length = 0;       // 记录第一条纸带当前已用长度

    // 我们必须按顺序取前 x 个单词，所以就从头开始循环遍历
    for (int i = 0; i < n; ++i) {
        std::string word;
        std::cin >> word;

        // 检查加上这个新单词后，总长度会不会超过 m
        if (current_length + word.length() <= m) {
            // 喵~ 还能放得下！
            current_length += word.length(); // 更新已用长度
            words_on_first_strip++;          // 单词数+1
        } else {
            // 呜...这个单词放不下了。
            // 因为必须是连续的前缀，所以这个单词和后面的所有单词都不能放了。
            // 为了正确处理多组测试数据，我们需要把这个测试用例剩下没读的输入都读掉。
            for (int j = i + 1; j < n; ++j) {
                std::string dummy;
                std::cin >> dummy; // 把剩下的单词读进来，但是什么也不做
            }
            break; // 结束当前测试用例的循环
        }
    }

    // 输出最终结果
    std::cout << words_on_first_strip << std::endl;
}

int main() {
    setup_io(); // 调用加速函数

    int t; // 测试用例的数量
    std::cin >> t;
    while (t--) { // 循环 t 次，解决每一个测试用例
        solve();
    }

    return 0;
}

题目大意 ​

解题方法 ​

题解代码 ​

相关知识点介绍 ​

题目大意

解题方法

题解代码

相关知识点介绍