C.小红打怪
1.题目:
2.样例
输入
5
1 2 3 4 5
输出
2
说明
第一回合,小红攻击全体怪物,队友1攻击5号怪物,队友2攻击4号和5号怪物,剩余每只怪物血量为[0,1,2,2,2]。
第二回合,小红攻击全体怪物,队友1攻击5号怪物,队友2攻击3号和4号怪物,即可击杀所有怪物。
3.思路
其实这题就是心里想的那样的,我当时以为有什么简单的方法,没想到就是暴力过的
我们用二分答案法,从1——数组中的最大值,如果mid满足条件,则用res保存答案,向左边二分,找到最小的回合数;不满足条件,不保存答案,向右边二分。
那么这个条件是什么呢?
我们在确定了回合数的情况下,怎么判断是否满足条件,我们先使用小红的技能,用数组b记录怪兽剩余的血量,再使用队友二的范围攻击,为了不浪费技能,我们一定要确保相邻的两个怪兽有血量,且是刚好使该怪兽血量变为零,如果没有相邻两个怪兽有血量,那么把剩余的队友二的技能次数跟队友一的技能次数合并相加,就当作单个技能技能攻击使用,然后不断的枚举怪兽的剩余血量,如果还有血量,就清零,把技能使用次数也减少,如果技能使用次数变为负数或者i没有到n+1,这说明这个回合数不满足条件。
具体代码实现:
#include <iostream>
using namespace std;
const int N = 1e5+10;
int n,m,res;
int a[N],b[N];bool check(int x){b[0]=0;int x1=x;for(int i=1;i<=n;i++){b[i]=a[i]-x;if(b[i]>0&&b[i-1]>0){int t=min(b[i],b[i-1]);t=min(x1,t);x1-=t; //不用弄额外的条件去限制x1//因为x1最后一定是>=0,因为t=min(t,x1) b[i]-=t;b[i-1]-=t;}}int x2=x+x1;int i=1;for(;i<=n;i++){if(b[i]>0){x2-=b[i];b[i]=0; }if(x2<0)break;}if(i==n+1&&x2>=0){return true;}else{return false;}
} void solve(){int l=1,r=m;while(l<=r){int mid=l+(r-l)/2;if(check(mid)){res=mid;r=mid-1;}else{l=mid+1;}}printf("%d\n",res);
}int main(void){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];m=max(m,a[i]);}solve();return 0;
}