GYM103660L.Monster Tower 整体二分

GYM103660L.Monster Tower

题目思路

有一个高$n$层的塔，塔的每层有一个怪兽，怪兽拥有$a_i$的血量，初始血量为$x$，击败第$i$层后可以获得该层怪兽的血量(即$x+=a[i]$)，当且仅当$x\ge a[i]$时才可以击败该怪兽。每次只能选择底$k$层的怪兽进行攻击。问最小的$x$。

容易发现答案具有单调性，因此考虑二分答案。$check$的时候使用优先队列维护底$k$层的怪兽血量，当堆顶的血量大于当前血量时不合法。

数组是2e5

Code

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10;
int a[N], s[N];

inline void solve(){
    
    int n = 0, k = 0; cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    auto check = [&](int mid){
    
        priority_queue<int, vector<int>, greater<int>> pq;
        int stn = mid;
        int pos = 1; while(pos <= k) pq.emplace(a[pos++]);
        while(pq.size()){
    
            if(stn < pq.top()) return false;
            else{
    
                stn += pq.top();
                pq.pop();
                if(pos <= n) pq.emplace(a[pos++]);
            }
        }
        return true;
    };
    int l = 0, r = *max_element(a + 1, a + 1 + n), ans = 0;
    while(l <= r){
    
        int mid = l + r >> 1;
        if(check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << endl;

}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}