CF1918D Blocking Elements 题解

· · 题解

感觉比 C 题还简单啊。

答案显然具有单调性，因此考虑二分转化为判定性问题。

假设我们要求代价不超过 mid，那么限制就是拿出来的数字之和不超过 mid，拿出来的数字分成的每一段的和不超过 mid。

考虑 dp，在保证每一段的和不超过 mid 的前提下，维护拿出来的数字和的最小值：设 f_i 表示强行拿出来 a_i 的情况下，[1,i] 中拿出来的数的和的最小值，转移平凡：

f_{i}=\min_{s_{i-1}-s_{j}<mid}\{f_j+a_i\}

其中 s_i=\sum_{j=1}^i a_j，也就是前缀和。

不难发现直接转移是 O(n^2) 的，但是注意到随着 i 的增大，j 一定不会变小，换句话说取 \min 的区间是个滑动窗口，单调队列优化即可将 dp 过程优化到 O(n)。

注意的一点是，只需要存在一个 f_i 满足 f_i\le mid 且 s_n-s_i\le mid 就满足条件了。

时间复杂度 O(n\log n)。

赛时偷懒写的小根堆，复杂度会多一个 \log。

#include<bits/stdc++.h>
#define int long long
#define For(i, a, b) for(int i = (a); i <= (b); i++)
#define Rof(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 5e5 + 5;
int n, a[N], f[N], sum[N];
bool check(int mid){
    For(i, 1, n) f[i] = 1e18;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
    q.push({0, 0}); f[0] = 0; int pos = 0;
    For(i, 1, n){
        while(pos + 1 < i && sum[i - 1] - sum[pos] > mid) pos++;
        while(q.top().second < pos) q.pop();
        f[i] = q.top().first + a[i];
        q.push({f[i], i});
    }
    For(i, 1, n) if(f[i] <= mid && sum[n] - sum[i] <= mid) return true; 
    return false;
}
void Solve(){
    cin >> n;
    For(i, 1, n) cin >> a[i];
    For(i, 1, n) sum[i] = sum[i - 1] + a[i];
    int l = 0, r = 1e16, ans = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    cout << ans << '\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T = 1; cin >> T;
    while(T--) Solve();
    return 0;
}