CF1692E

Hooch · 2022-06-30 22:13:38 · 题解

题目大意

给出 n 个数，每个数为 0 或 1。你可以选择从两边删数，求至少删几个数才可以使剩下的数总和为 s 。

如果不能达到 s ，则输出 -1 。

基本思路

无解的情况很好判，若不删数都没法到 s 个，那么一定无解。

然后我们想有解的情况该如何删数。

我们发现我们删完数后剩下的一定是一段连续的区间 [l,r]。那么我们就可以把问题转化成选取一段最长的，和为 s 的区间 [l,r]。

那么我们处理出前缀和 sum_i，只需要在知晓 [l,r] 的情况下 O(1) 判断就行了。

但是这道题不允许暴力枚举 [l,r]，我们考虑优化。

很显然，sum_i 是一个单调不严格上升的序列。我们可以在上面二分。

于是我们枚举起点 l，然后二分查找到值为 sum_{l-1}+s 的 sum_r 即可。

代码

#include <bits/stdc++.h>
using namespace std;
int s[200005]; 
main() {
    int t; cin >> t; while (t--) {
        int n, k; cin >> n >> k;
        for (int i = 1; i <= n; ++i) {int x; cin >> x; s[i] = s[i - 1] + x;}
        if (k > s[n]) {cout << -1 << endl; continue;}
        int p = -0x3f3f3f3f, L, R;
        for (int i = 1; i <= n; ++i) {
            int l = i, r = n, ans = 0;
            while (l < r)  {
                int mid = l + r + 1 >> 1;
                if (s[mid] - s[i - 1] <= k) l = mid;
                else r = mid - 1;
            }
            if (!l) continue;
            ans = l - i + 1;
            p = max(p, ans);
        }
        cout << (p == -0x3f3f3f3f ? -1 : (n - p)) << endl;
    }
}