题意:你遇到了N个怪兽,你可以选择其中一头怪兽进行攻击,它将会受到a点伤害值,其他怪兽获得b点伤害值(b<a)。当一个怪兽的hp为0时他将会消失,求攻击的最少次数。


题解:选择最大的进行攻击肯定不是最优,这题可以用二分答案来解。假设当前攻击次数为mid,那么每头怪兽收到的攻击就是mid*b,剩下要是还有值则选用a的伤害值来攻击,看最后是否能够把每头怪兽消灭掉,如果能消灭那么就将右区间减少,否则增加左区间。


代码:

#include <iostream>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <sstream>
using namespace std;
 
typedef long long LL;
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
#define memset(a,b) memset(a,b,sizeof(a))
#defineGE() printf(">----------\n")
#defineIN() freopen("in.txt","r",stdin)
#defineOUT() freopen("out.txt","w",stdout)
const int mod=1000000007;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=100005;
 
LL n, a, b;
LL data[maxn];
 
 
bool check(LL mid){
   LL sta=0;
   for(int i=0;i<n;i++){
       LL have=data[i]-mid*b;
       if(have>0){
           sta+=ceil(have*1.0/(a-b));
           if(sta>mid)return 0;
       }
   }
   return 1;
}
 
 
int main()
{
   while(~scanf("%lld%lld%lld", &n, &a, &b)){
       LL l=0, r=0;
       for(int i=0;i<n;i++){
           scanf("%d", &data[i]);
           r=max(r, data[i]);
       }
       while(l<r){
           int mid=(r+l)>>1;
           if(check(mid))r=mid;
           else l=mid+1;
       }
       printf("%d\n", l);
   }
   return 0;
}