题解：CF2089B2 Canteen (Hard Version)

chrisgr · 2025-10-16 19:49:00 · 题解

题目很快就切了，全靠 tag 打的好。
做不出题怪大脑，胡出来题自称佬。

注意到答案上界为 n 所以暴力模拟的操作次数为 n ^ 2 次 ，不可接受。注意到对于每次操作的 a_i 和 b_i 其中必然有一个会清零，对于为零的值我们的操作实际上没有意义，所以我们本质上有意义的操作只有 n 次。

考虑如何模拟过程中只模拟有意义操作，注意到可以用一个单调队列维护当前位置以及前面的 a。对于一个位置 i，要么 b_i 清零，要么 单调队列清空，操作次数只有 n 次，可以接受。

那有人就要问了，这只是 easy 版的做法，那 hard 版呢？莫慌莫慌，听我徐徐道来。我们可以二分答案，用上面的方法检验答案是否合法。这样时间复杂度为 O(n \log n)，可以通过。

code

#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n, a[N], b[N];
long long k;
inline bool check(int x) {
    int aa[N], bb[N];
    long long ret = 0;
    deque<int> q;
    for(int i = n; i; --i) 
        aa[i] = a[i], bb[i] = b[i];
    for(int i = 1; i <= n; ++i) {
        q.push_back(i);
        while(!q.empty() && i - q.front() + 1 > x) 
            ret += aa[q.front()], q.pop_front();
        if(ret > k) return 0;
        while(!q.empty() && bb[i] >= aa[q.back()]) 
            bb[i] -= aa[q.back()], q.pop_back();
        if(!q.empty()) 
            aa[q.back()] -= bb[i], bb[i] = 0;
    }
    for(int i = 1; !q.empty() && i <= n; ++i) {
        while(!q.empty() && n - q.front() + i + 1 > x) 
            ret += aa[q.front()], q.pop_front();
        if(ret > k) return 0;
        while(!q.empty() && bb[i] >= aa[q.back()]) 
            bb[i] -= aa[q.back()], q.pop_back();
        if(!q.empty()) 
            aa[q.back()] -= bb[i], bb[i] = 0;
    }
    return 1;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        cin >> n >> k;
        for(int i = 1; i <= n; ++i) cin >> a[i];
        for(int i = 1; i <= n; ++i) cin >> b[i];
        int l = 0, r = n;
        while(l <= r) {
            int mid = l + r >> 1;
            if(check(mid)) r = mid - 1;
            else l = mid + 1;
        }
        printf("%d\n", r + 1);
    }
    return 0;
}