题解：CF2052J Judicious Watching

· · 题解

提供一篇二分类型题解作为参考。

思路

首先分析怎样完成作业是最优的。很明显完成时间越靠前越早完成越好，在此基础上完成作业所需时间少的越早完成越好（即以 (d_i,a_i) 为二元组从小到大依次完成）。

我们容易发现，直接二分答案具有单调性。设其中一次二分的答案下的看剧的时间为 x。考虑如何检查答案。

为了尽可能地在规定时间内完成作业，贪心地先将看剧的时间放在 (t_k-x,t_k] 的时间段中，在 [1,t_k-x] 和 [t_k,+\infty) 的时间段中完成作业。通过前缀和预处理和一次二分查找可以将 [1,t_k-x] 的时间段中能够完成的（最多）作业数量求出来。可以发现大多数情况时间会有剩余，记真实的完成时间为 s，那么我们就可以将看剧的时间放至 (s,s+x] 的时间段。那么剩下一部分作业就应该从 s+x+1 的时间开始完成。若现在要完成 [c,n] 的作业，容易发现对于每个正整数 i\in[c,n] 要满足

s+x+\sum_{j=c}^{i}{a_j}\le d_i

考虑如何维护这一式子，将和拆开，变为

s+x+\sum_{j=1}^{i}{a_j}-\sum_{j=1}^{c-1}{a_j}\le d_i

将不变项都移到右边，得到

s+x-\sum_{j=1}^{c-1}{a_j}\le d_i-\sum_{j=1}^{i}{a_j}

和可以通过前缀和优化，记为数组 sum，则 s=sum_{c-1}，有

\begin{equation} \begin{aligned} sum_{c-1}+x-sum_{c-1}\le d_i-sum_i\\ x\le d_i-sum_i \end{aligned} \nonumber \end{equation}

由于 x 是个定值，我们要使每个正整数 i\in[c,n] 满足 x\le d_i-sum_i，也就是使 x\le \min_{i=c}^n\{d_i-sum_i\}。容易发现是一段后缀最小值，预处理出来就可以了。当然如果 c>n，就不必再满足这个式子。

代码

实现可能有略微不同，仅供参考。 

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fer(i, a, b) for(int i = (a); i <= (b); i ++)
#define fel(i, a, b) for(int i = (a); i >= (b); i --)
#define LL long long
const int N = 2e5 + 10; 
int T; 
int n, m, q; 
struct node { LL a, d; } a[N]; 
LL xa[N], xd[N]; 
LL b[N]; 
bool check(LL tk, LL z) {
    int t = upper_bound(xa + 1, xa + n + 1, tk - z) - xa - 1; 
    return t == n || z <= xd[t + 1]; 
}
signed main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr); 
    cin >> T; 
    LL tk; 
    while(T --) {
        cin >> n >> m >> q; 
        fer(i, 1, n) cin >> a[i].a; 
        fer(i, 1, n) cin >> a[i].d; 
        fer(i, 1, m) cin >> b[i]; 
        sort(a + 1, a + n + 1, [](node a, node b) { return tie(a.d, a.a) < tie(b.d, b.a); }); 
        fer(i, 1, m) b[i] += b[i - 1]; 
        fer(i, 1, n) {
            xa[i] = xa[i - 1] + a[i].a; 
            xd[i] = a[i].d - xa[i]; 
        }
        xd[n + 1] = LONG_LONG_MAX; 
        fel(i, n - 1, 1) xd[i] = min(xd[i + 1], xd[i]); 
        while(q --) {
            cin >> tk; 
            int l = 1, r = upper_bound(b + 1, b + m + 1, tk) - b - 1, mid; 
            int ans = 0; 
            while(l <= r) {
                mid = (l + r) >> 1; 
                if(check(tk, b[mid])) {
                    ans = mid; 
                    l = mid + 1; 
                } else r = mid - 1; 
            }
            cout << ans << ' '; 
        }
        cout << endl; 
    }
    return 0; 
}