题解：P10605 下头论文

George222 · 2024-06-20 18:26:45 · 个人记录

本题是一道模拟题

题意

有 n 个任务要依次完成，每个任务要连续做 a_i 天；给定一些天数 b_i，在天 b_i 的时候不能做任务，在完成一个任务的时间里不能完成另一个任务。

求最少能在几天后完成所有任务。

思路

因为要求最短的时间，所以我们不要浪费掉任何一个可以完成当前任务的空闲时间。空闲时间就是在 b_i 和 b_{i + 1} 之间，我们可以遍历 b 来确定是否能在此时间内完成当前任务。

代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[100005], b[100005];
int ans = 1;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i ++)
        cin >> b[i];

    int i = 1, now = 1;
    while (i <= n) // 遍历任务
    {
        bool f = 1;
        for (int j = now; j <= m; j++) // 遍历忙碌的天
        {
            if (b[j] > ans + a[i] - 1)
                break;
            if (b[j] < ans)
                break;
            if (b[j] >= ans && b[j] <= ans + a[i] - 1)
            {
                f = 0;
                ans = b[j] + 1;
                now = j + 1;
                break;
            }
        }
        if (f == 1)
        {
            ans = ans + a[i];
            i++;
        }
    }
    cout << ans - 1 << "\n";
    return 0;
}

/*
至于为什么要 ans - 1
我们在 ans += ans + a[i];
是将 ans 变为任务结束的后一天来避免有重叠的情况
所以判断和输出时要 -1，而加入时间时不 -1
*/

AC记录