题解 | #小红购买装备#

题目要求满足条件的最小回合数，可以使用二分来求解

• 在x回合内，首先进行整体攻击（小红），然后再进行双消（队友1），最后统计剩余总血量，进行单体攻击（队友2）和无法双消剩下的攻击（队友1），比较是否可以消除完剩余血量

#include <bits/stdc++.h>
using namespace std;
long long n, a[100010], ans, Max = -1;
bool round(int x) {//进行的回合数
    long long temp[100005];
    for (int i = 1; i <= n; i++) {
        temp[i] = a[i] - x;//整体攻击（小红）
    }

    long long cnt = 0, sum = 0;
    for (int i = 1; i < n; i++) {//双消部分（队友1）
        if (temp[i] > 0 && temp[i + 1] > 0) {
            cnt += min(temp[i], temp[i + 1]);//可以双消的次数
            int tmp = min(temp[i], temp[i + 1]);
            temp[i] -= tmp;//双消后的值
            temp[i + 1] -= tmp;
        }
		if(cnt>=x) break;// 双消次数不能大于回合数
    }
    for (int i = 1; i < n; i++) {
        if (temp[i] > 0)
            sum += temp[i];//剩余怪的血量
    }
    return sum <= 2 * x - cnt;//如果剩下的血量能被打完，就返回1，否则返回0
    	//x为回合数，x为队友1能造成单击伤害，x-cnt表示（没有双消目标）后进行的攻击伤害
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] > Max) {
             Max = a[i];//找到血量最大值
        }
    }

    int l = 0, r = Max;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (round(mid)) {
            r = mid - 1;//满足，则看看更小的回合可不可以
            ans = mid;
        } else {
            l = mid + 1;//不满足，则看看更大的回合
        }
    }//直到确定最小回合数

    cout << ans;
    return 0;
}