【提问】求最早完成的天数

Question

题目是这个：
The head of human resources department decided to hire a new employee. He created a test exercise for candidates which should be accomplished in at most m working days. Each candidate has to pass this test exercise. During the j-th day a candidate is allowed to be in the office for at most tj units of time.
人力资源部的负责人决定雇用一名新员工。他为候选人们设置了一个测试练习，该练习最多可以在m 个工作日内完成。每个考生都必须通过这个测试练习。在第j天，候选人最多可以在办公室待tj个单位的时间。
Overall, n candidates decided to apply for the job and sent out their resumes. Based on data received the head has defined two parameters describing every candidate: di and ri. The parameter di is the time to get prepared for work which the i-th candidate spends each morning. This time doesn't depend on day. The parameter ri is the total working time needed for the i-th candidate to accomplish the whole test exercise.
总而言之，n 名候选人决定应聘这份工作并投递了他们的简历。根据收到的数据，负责人定义了两个参数来描述每个候选者：di 和 ri 。参数 di 是第i个候选人每天早上为工作做准备的时间。这个时间不取决于工作日。参数ri 是第i个候选者完成整个测试练习所需的总工作时间。
Thus the time spent in the office in the j-th day consists of di units of time to get prepared and some units of time to proceed with the exercise. A candidate can skip entire working day and do not come to the office. Obviously in this case he doesn't spend di units of time to prepare.
因此，第j天在办公室度过的时间包括 di 个单位的准备时间和进行测试练习的时间。候选人可以跳过整个工作日，不来办公室。显然，在这种情况下，他不用花 di 个单位的时间来准备。
To complete the exercise a candidate should spend exactly ri units of time working on the exercise (time to prepare is not counted here).
为了完成练习，候选人应该花整整 r 个单位的时间在练习上（这里不计算准备时间）。
Find out for each candidate what is the earliest possible day when he can fully accomplish the test exercise. It is allowed to skip working days, but if candidate works during a day then he must spend di units of time to prepare for work before he starts progressing on the exercise.
为每位考生找出他可以完全完成测试练习的最早一天。可以跳过工作日，但如果候选人在某一天选择工作，那么他必须花 d 个单位的时间来准备工作，然后才能开始练习。

Input 输入
The first line contains two integer numbers n,m (1≤n,m≤2·105)−the number of candidates and the maximum number of working days to do the test exercise.
第一行包含两个整数 n，m（1≤n，m≤2·10 5 ）分别为考生人数和进行测试练习的最大工作日数。
The second line contains m integer numbers t1,t2,...,tm (1≤tj≤106)− the durations of working days in time units.
第二行包含 m 个整数t1,t2,...,tm (1≤tj≤106)，为以时间单位表示的工作日可工作时间。
The following n lines contain two integers each: di,ri (0≤di≤106,1≤ri≤106)− how much time in the beginning of a day is required for i-th candidate before he starts his work on the test exercise and how much time it is needed for him to accomplish this task.
以下 n 行每行包含两个整数：di,ri (0≤di≤106,1≤ri≤106)，为第i个考生的准备时间，以及他需要多少时间才能完成这项任务。
Output 输出
Output a sequence of n integer numbers b1,b2,...,bn, where bi is the earliest day when the i-th candidate can finish the test exercise.
输出 n 个整数 b1,b2,...,bn, 的序列，其中bi 是第i个候选者可以完成测试练习的最早一天。
In case the i-th candidate cannot finish the test exercise in m days output bi=0.
如果第i个考生无法在 m 天内完成测试练习，则输出 bi =0。
Days in this problem are numbered from 1 to m in the order they are given in the input.
此问题中的天数按输入中给出的顺序从 1 到 m 编号。

测试用例：
Input
3 3
4 2 5
1 3
2 5
3 4
Output
1 3 0

我不明白为什么输出的第二个是3？对于第二位应聘者来说，要找出最早的一天，只要第一天和第三天去就行了吧？为什么要去三天？

Answer 1

引自免费微信小程序：皆我百晓生

首先，让我们逐个分析每个候选人的情况。

对于第二个候选人，其参数为 di = 2，ri = 5。这意味着每天开始时他需要 2 单位时间来准备，而他总共需要花费 5 单位时间来完成测试练习。

输入的工作日时长分别为 t1 = 4, t2 = 2, t3 = 5。

• 第一天：该候选人可以工作的时间是 4 - 2 = 2 单位时间（减去准备时间）。
• 第二天：可工作时间为 2 单位时间。
• 第三天：可工作时间为 5 - 2 = 3 单位时间（减去准备时间）。

由于第一天和第二天加起来只有 2 + 2 = 4 单位时间，不足以完成整个练习（需 5 单位时间），所以他必须在第三天也工作。这样，在第一天工作2单位时间，第二天不工作，第三天工作3单位时间，正好可以在三天内完成测试练习。

因此，输出的 bi = 3 表示他最早能在第三天完成测试练习。

现在我将提供一个 C++ 的解决方案代码：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<int> work_days(m);
    for (int i = 0; i < m; ++i) {
        cin >> work_days[i];
    }
    
    vector<pair<int, int>> candidates(n);
    for (int i = 0; i < n; ++i) {
        cin >> candidates[i].first >> candidates[i].second;
    }
    
    vector<int> results(n, 0);
    for (int i = 0; i < n; ++i) {
        int di = candidates[i].first;
        int ri = candidates[i].second;
        int accumulated_time = 0;
        int day_count = 1;
        
        for (day_count = 1; day_count <= m; ++day_count) {
            if (work_days[day_count - 1] >= di && accumulated_time + (work_days[day_count - 1] - di) <= ri) {
                accumulated_time += (work_days[day_count - 1] - di);
                if (accumulated_time == ri) {
                    break;
                }
            }
        }
        
        if (accumulated_time == ri) {
            results[i] = day_count;
        }
    }
    
    for (int result : results) {
        cout << result << " ";
    }
    cout << endl;
    
    return 0;
}

这段代码首先读取输入数据，然后遍历每个候选人，计算他们在给定工作日内完成任务所需的最早天数，并将结果存储在 results 向量中。最后，它会输出每个候选人的最早完成天数。