题解 | 不想做二分题

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
vector<int>a;
int n ; 
int sum ; 
bool check(int x)
{
    vector<int> b = a;
    for (int i = 0; i < n; i++) 
    {
        b[i] = max(0LL, b[i] - x);
    }
    
    int k = 0;  // 有效范围攻击次数
    // 贪心：优先用范围攻击打相邻都有血量的怪物
    for (int i = 0; i < n - 1; i++) 
    {
        int d = min(b[i], b[i + 1]);
        d = min(d, x - k);  // 不超过x次范围攻击，用x - k来代表剩余的攻击次数，保证所进行的操作始终满足次数
        b[i] -= d;
        b[i + 1] -= d;
        k += d;//已经进行的攻击操作
        if (k == x) break;//检测到攻击次数超过上限 
    }
    
    // 计算最终剩余血量
    int final_remain = 0;
    for (int i = 0; i < n; i++) 
    {
        final_remain += b[i];
    }
    
    // 范围攻击k次有效，x-k次浪费，加上x次单体攻击
    return final_remain <= 2 * x - k;//由于x - k最小为0 ， 所以无需进行max(0LL ， x - k);

}
void work() 
{
    cin >> n ;
    a.resize(n);
    int maxi = 0 ; 
    for(int i = 0 ; i < n ; i++)
    {
        cin >> a[i];
        maxi = max(maxi , a[i]);
        sum += a[i];
    }
    int l = 0 , r = maxi ;
    while(l < r)
    {
        int mid = (l + r) >> 1 ; 
        if(check(mid))
        {
            r = mid ; 
        }
        else
        {
            l = mid  + 1 ; 
        }
    } 
    cout << l << endl ; 
}
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t--) 
    {
        work();
    }
    return 0;
}

这道题目出现在二分里面，但是又不能让我们进行排序破坏题目原有的条件，所以考虑使用二分答案的思想，通过对操作次数的检验，不断缩小区间，最后得到最小的回合数，需要额外注意的是check函数的书写