猫娘酱的算法小课堂：Codeforces 4B - 考前复习时间表喵~

哈喽，各位主人，你们好呀~ 我是你们最贴心的小助手猫娘酱！今天我们要解决的是一道关于时间规划的可爱问题，就像帮贪玩的小主人安排写作业的时间一样，很有趣的喵~

一起来看看 Peter 同学遇到了什么麻烦吧！

---

题目大意

明天就要考生物了，Peter 同学有点小慌张。在过去的 d 天里，他每天都进行了一点学习。他严格的父母要求他，在第 i 天，学习时间不能少于 minTime_i 小时，也不能多于 maxTime_i 小时。

现在，Peter 只记得自己总共学习了 sumTime 小时，却忘了每天具体学了多久。他需要拿出一份具体的学习计划表（每天学习了多少小时）给父母看。

我们的任务就是，判断 Peter 能不能构造出一份满足以下条件的学习计划：

1. 总共有 d 天。
2. 第 i 天的学习时间 schedule_i 必须在 [minTime_i, maxTime_i] 的区间内。
3. 所有 d 天的学习时间加起来，总和必须等于 sumTime。

如果可以构造出这样一份计划，我们就输出 "YES"，并在下一行给出任意一种可行的计划。如果不行，就输出 "NO"。

简单来说，就是要把 sumTime 这个总数，分配到 d 天里，并且每一天的分配量都要满足各自的最小和最大限制，喵~

---

解题思路

这个问题看起来有点复杂，但其实只要理清思路，就像猫咪找到最舒服的午睡地点一样简单！我们可以用一种叫做 贪心 的策略来解决它，喵~

第一步：判断问题是否“有解”

在动手分配时间之前，我们得先看看 Peter 的要求是不是“天方夜谭”。

1. 计算总的最小学习时间 (minTotalTime)： 就算 Peter 每天都只按最少时间学习，他总共需要学习多少小时呢？很简单，把每天的 minTime_i 全都加起来就好啦。 minTotalTime = minTime_1 + minTime_2 + ... + minTime_d

2. 计算总的最大学习时间 (maxTotalTime)： 同理，就算 Peter 每天都拼命学到最晚，他最多能学习多少小时呢？就是把每天的 maxTime_i 全都加起来。 maxTotalTime = maxTime_1 + maxTime_2 + ... + maxTime_d

现在，我们有了 Peter 可能学习时间的总范围 [minTotalTime, maxTotalTime]。他实际学习的总时间 sumTime 必须落在这个范围里才行。

• 如果 sumTime < minTotalTime，说明就算每天都按最少的学，总时间也超了。这不可能做到，就像小猫咪不可能一天就长成大老虎一样，喵！
• 如果 sumTime > maxTotalTime，说明就算每天都学满了，总时间也凑不够。这也办不到！

所以，只要 sumTime 不在 [minTotalTime, maxTotalTime] 这个区间内，我们就可以直接断定 "NO"，问题解决！

第二步：贪心构造一个解

如果 sumTime 恰好在 [minTotalTime, maxTotalTime] 区间内，那么答案就一定是 "YES"！因为这意味着一定存在一种分配方案。现在我们的任务就是找出其中一种。

本喵的贪心小策略是这样的：

1. 先满足最低要求：我们先假设 Peter 每天都只学习了 minTime_i 小时。这样，我们就构造出了一个基础的时间表 schedule，其中 schedule_i = minTime_i。这个基础时间表的总时长就是我们刚才算的 minTotalTime。

2. 计算还需要“额外”分配的时间：Peter 实际学习的总时间是 sumTime，而我们基础计划的总时间是 minTotalTime。那么，还剩下 remainingTime = sumTime - minTotalTime 小时需要分配到各个天中去。

3. 贪心地分配剩余时间：现在，我们从第 1 天开始，依次往后检查。对于第 i 天：

   • 它最多还能增加多少学习时间呢？是 maxTime_i - minTime_i。
   • 我们把 remainingTime 中的一部分加给第 i 天。加多少呢？当然是越多越好，但不能超过当天能增加的上限。所以，我们实际能增加的时间是 min(remainingTime, maxTime_i - minTime_i)。
   • 给第 i 天增加了时间后，别忘了更新 remainingTime 哦。
   • 然后继续对下一天做同样的操作，直到 remainingTime 变成 0 为止。

因为我们已经保证了 sumTime <= maxTotalTime，所以这个 remainingTime 一定能被完全分配完，不用担心不够位置放，喵~

当 remainingTime 分配完毕后，我们就得到了一个完美的、满足所有条件的学习计划啦！

---

题解代码 (C++)

这是本喵根据上面的思路写好的代码，加了一些注释，方便主人理解哦~

#include <iostream>
#include <vector>
#include <numeric> // 用来求和，不过我们这里是手动循环求和
#include <algorithm> // 用来使用 min 函数

void solve() {
    int d, sumTime;
    std::cin >> d >> sumTime;

    // 用两个 vector 来存放每天的最小和最大学习时间，喵~
    std::vector<int> minTimes(d);
    std::vector<int> maxTimes(d);
    
    // 计算总的最小和最大学习时间
    int minTotalTime = 0;
    int maxTotalTime = 0;

    for (int i = 0; i < d; ++i) {
        std::cin >> minTimes[i] >> maxTimes[i];
        minTotalTime += minTimes[i];
        maxTotalTime += maxTimes[i];
    }

    // 第一步：判断是否可能有解
    if (sumTime >= minTotalTime && sumTime <= maxTotalTime) {
        // 如果有解，就大声说 YES！
        std::cout << "YES\n";
        
        // 第二步：开始构造解
        // 先让每天都等于最小学习时间，这是我们的基础计划
        std::vector<int> schedule = minTimes;
        
        // 计算还需要额外分配多少时间
        int remainingTime = sumTime - minTotalTime;
        
        // 第三步：贪心地把 remainingTime 分配下去
        for (int i = 0; i < d; ++i) {
            // 如果时间都分完了，就提前结束循环，喵~
            if (remainingTime <= 0) {
                break;
            }
            
            // 计算第 i 天最多还能增加多少学习时间
            int canAdd = maxTimes[i] - minTimes[i];
            
            // 决定这次要给第 i 天增加多少时间
            // 不能超过剩余时间，也不能超过当天能增加的上限
            int addNow = std::min(remainingTime, canAdd);
            
            // 更新第 i 天的计划，并扣除用掉的剩余时间
            schedule[i] += addNow;
            remainingTime -= addNow;
        }
        
        // 把最终的计划打印出来~
        for (int i = 0; i < d; ++i) {
            std::cout << schedule[i] << (i == d - 1 ? "" : " ");
        }
        std::cout << "\n";
        
    } else {
        // 如果总时间不在范围内，那就没办法啦，只能说 NO
        std::cout << "NO\n";
    }
}

int main() {
    // 这两行是为了让输入输出快一点，是竞赛小技巧哦~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    solve();
    
    return 0;
}

---

知识点介绍：贪心算法 (Greedy Algorithm)

这道题的核心就是 贪心算法 啦！

什么是贪心算法呢？

想象一下，一只小猫咪面前有一堆大小不一的鱼干。如果它采用贪心策略，它会每次都毫不犹豫地选择当前看起来最大、最美味的那一条鱼干吃掉，而不会去想“如果我先吃小的，会不会后面能吃到更多”这种复杂的问题。

贪心算法就是这样，它在每一步决策时，都采取当前状态下最好或最优的选择，并期望通过一系列的局部最优选择，最终能够产生一个全局最优解。

为什么这道题可以用贪心？

在这道题里，我们需要分配的“资源”是 remainingTime。分配给哪一天其实是“无差别”的，只要不超过那一天的 maxTime 就行。给第一天增加 1 小时和给第二天增加 1 小时，对于“消耗 remainingTime”这个目标来说，效果是一样的。

因此，我们不需要做复杂的权衡。从第一天开始，有多少空余容量（maxTime - minTime），就尽量用 remainingTime 去填满它，这种简单直接的策略是完全有效的。我们做的局部最优选择（“给当前这天尽量多加时间”）最终能够导向一个正确的全局解。

好啦~ 这就是 Codeforces 4B 的全部解析了！是不是很简单呢？只要跟着猫娘的思路一步步来，再复杂的难题也能迎刃而解！主人下次遇到问题，也随时可以来找我哦~ 喵~