GYM103660L.Monster Tower 整体二分

GYM103660L.Monster Tower 题目思路

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

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

数组是2e5

Code

#include 
#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 > a[i];
    auto check = [&](int mid){
        priority_queue pq;
        int stn = mid;
        int pos = 1; while(pos