题解：P10605 下头论文

xuan_never · 2024-06-20 15:04:07 · 题解

来水一篇较短解法。

思路

看题解都是离线做的，我来讲下在线做法。
每次可以通过记录上一个非空闲的日子，直接算出可以用来做任务的天数，因为任务的顺序是固定的，所以直接进行判断是否可以做任务即可。

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, a[100005], b, ru, an, l;
// an 为答案，ru 用来记录上一个非空闲的日子， l 表示空闲的日子数
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m;
    for (int i = n; i >= 1; --i)
        cin >> a[i]; // 倒序输入，省一个变量
    for (int i = 1; i <= m; ++i) {
        cin >> b;
        l = b - ru - 1, ru = b;
        while (n && a[n] <= l) // 按顺序判断
            l -= a[n], an += a[n--];
        if (!n) break;
        an = b;
    } while (n) an += a[n--];
    cout << an;
    return 0;
}