GYM103660L. Monster tower overall dichotomy

GYM103660L.Monster Tower

Topic ideas

There is a high $n$ Tower on the first floor , There is a monster on each floor of the tower , Monsters have $a_i$ HP , Initial health is $x$, Defeat number $i$ After this layer, you can get the blood volume of the monster in this layer ( namely $x+=a[i]$), If and only if $x\ge a[i]$ Only then can we defeat the monster . Only the bottom can be selected at a time $k$ Tier monsters attack . Ask the smallest $x$.

It is easy to find that the answer is monotonous , So consider the dichotomous answer .$check$ When using the priority queue to maintain the bottom $k$ The monster's HP of layer , It is illegal when the health at the top of the heap is greater than the current health .

An array is 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;
}