题目描述

给你一个长度为n的数组，代表n道题目，每个题目有一个写题解的时间，选出长度为k的子序列，然后有两个人分别从前后选取一个前缀和后缀，并行完成写题解的过程，求两人都完成写题解的最短时间。

样例

输入

6
5 4
1 10 1 1 1
5 3
1 20 5 15 3
5 3
1 20 3 15 5
10 6
10 8 20 14 3 8 6 4 16 11
10 5
9 9 2 13 15 19 4 9 13 12
1 1
1

输出

2
6
5
21
18
1

二分 + 反悔堆

二分一下答案$mid$，并且分别求一下原数组的前缀和后缀不超过$mid$的情况下最多能选多少个题目。这里可以使用反悔堆来贪心地维护当前所选的数字，每一次将当前的数字加入优先队列，然后一直弹出堆顶元素（即堆中的最大元素）直到当前优先队列中元素值的总和不超过$k$，这样就可以求出在总和不超过$mid$的情况下，前缀和后缀分别最多能装下多少个元素。

时间复杂度

二分答案$O(log(1e15))$
每次check函数$O(nlogn)$
总的时间复杂度为$O(log(1e15) * n * logn)$

C++ 代码

//#pragma GCC optimize(2)
#include<bits/stdc++.h>

using namespace std;
#define input_fast std::ios::sync_with_stdio(false);std::cin.tie(0)
const int mo = 998244353;
typedef long long ll;

int n, a[300010], k;
ll pre[300010], suf[300010];

bool check(ll mid) {
    suf[n + 1] = 0;
    priority_queue<ll> q;
    ll now = 0;
    for (int i = 1; i <= n; i ++) {
        q.push(a[i]);
        now += a[i];
        while (now > mid) {
            now -= q.top();
            q.pop();
        }
        pre[i] = int(q.size());
    }
    while (!q.empty()) q.pop();
    now = 0;
    for (int i = n; i >= 1; i --) {
        q.push(a[i]);
        now += a[i];
        while (now > mid) {
            now -= q.top();
            q.pop();
        }
        suf[i] = int(q.size());
    }
    for (int i = 0; i <= n; i ++) {
        if (pre[i] + suf[i + 1] >= k) return true;
    }
    return false;
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    ll l = 0, r = 1e15;
    while (l < r) {
        ll mid = l + r >> 1;
        if (check(mid)) {
            r = mid;
        } else l = mid + 1;
    }
    cout << l << "\n";
}

int main() {
//    freopen("C:/Users/14842/CLionProjects/cf/in.txt", "r", stdin);
//    freopen("C:/Users/14842/CLionProjects/cf/out.txt", "w", stdout);
    int tt;
    cin >> tt;
    while (tt --) solve();
    return 0;
}