题解 | #小红打怪#

本题求几轮的攻击可以将所有怪兽消灭，明显是二分算法来求解，对于每个mid值，分三步来分析，可将所有攻击分为min次小红的攻击，mid次队友一的攻击，mid次队友二的攻击，先分析小红的攻击，每次攻击小红都使每个怪血量减一，所以mid轮攻击之后，每个怪的血量减少mid，然后分析队友二：每次都是让相邻的两个怪血量减一（注意，已经死的怪也可以参与此攻击），所以最优的方法就是，先让队友二充分地攻击两个活着的怪，用mid减去攻击次数得到队友二剩下的攻击次数（即打一活一死），最后把血量大于零的加在一起，定义为s，让队友一和队友二（用剩下的次数打）去攻击，即mid+队友二剩余的攻击次数>s，即为一个合理答案。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100010;
int n,a[N],b[N];
bool check(int mid)
{
    for(int i=1;i<=n;i++)b[i]=a[i]-mid;
    int x=mid;
    for(int i=1;i<n;i++)
    {
        if(b[i]>0&&b[i+1]>0)
        {
            int tt=min(x,min(b[i],b[i+1]));//最小攻击
            x-=tt,b[i]-=tt,b[i+1]-=tt;
        }
    }
    int s=0;
    for(int i=1;i<=n;i++)if(b[i]>0)s+=b[i];
    return mid+x>=s;//队友一+剩余的队友二（可以对死去的怪物尸体释放该技能）
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int l=1,r=1e9;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l;
    return 0;
}