玉米大炮

•  比赛主页
 
•  我的提交

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述 

小蓝正在玩一个植物大战僵尸的改版,在一个特别的关卡中,他需要用玉米大炮击溃僵王博士。 现在小蓝已经部署了 nn 个玉米大炮,对于第 ii 个玉米大炮,有一个伤害值 a_iai​ ,一个装填时间 b_ibi​ ,玉米大炮每次发射后需要 b_ibi​ 的装填时间,装填完毕之后才可以再次发射。 小蓝已经知道僵王博士有 mm 点生命值,但他不知道他什么时间可以击溃僵王博士,你需要计算出出小蓝最少需要多少时间可以击溃僵王博士。 小蓝可以同时控制所有玉米大炮, 玉米大炮每次对僵王博士的攻击会扣除等于其伤害值的血量,如果血量低于或者等于 00 ,僵王博士被消灭,僵王博士被永久冻结不会攻击,开始时所有玉米大炮都装填完毕,装填完毕后小蓝会直接控制其立即攻击,攻击所花费的时间忽略不计。

输入描述:

第一行两个个整数 nn , mm ( 1 \le n \le 10^{5} , 1 \le m \le 10^{9} )(1≤n≤105,1≤m≤109)。 接下来 nn 行,每行两个整数  a_iai​ , b_ibi​ (1 \le a_i \le 10^{9} , 1 \le b_i \le 10^{9})(1≤ai​≤109,1≤bi​≤109)。

输出描述:

输出一行一个整数,代表击溃僵王博士需要的最小时间。

示例1

输入

复制

3 3
1 1
2 2
3 3

输出

复制

0

说明

开始时,小蓝控制所有大炮立即发射炮弹,僵王博士受到 66 点伤害,直接被击溃。

示例2

输入

复制

2 20
5 1
5 3

输出

复制

2

说明

开始时,小蓝控制所有大炮立即发射炮弹,僵王博士受到 1010 点伤害, 一秒后一号大炮装填完毕,小蓝控制其攻击僵王博士,僵王博士收到 55 点伤害 , 两秒后一号大炮再次装填完毕小蓝再次控制其攻击僵王博士, 僵王博士再次收到 55 点伤害,僵王博士血量归 00 被击溃。

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>

using namespace std;
typedef __int128 ll;
const int mas=1e6+10;
ll a[mas],b[mas],n,m;

bool check(ll x)
{
	ll cnt=0;
	for(ll i=1;i<=n;i++)
		cnt+=((ll(x/b[i]+1))*a[i]);
	if(cnt>=m)return 1;
	return 0;
}
 
void one_half()
{
	ll l=0,r=1e18;
	while(l<r)
	{
		ll mid=l+r>>1;//r=mid====mid=l+r>>1; 
		if(check(mid))r=mid;
		else l=mid+1; 
	}
	printf("%lld\n",l);
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++)
		scanf("%lld%lld",&a[i],&b[i]);
	one_half();	
		
	 return 0;
}

题解给定 :

A 玉米大炮 给定 nnn 个玉米大炮,每个玉米大炮都有自己的攻击伤害和装填时间,何时可以击溃僵王博士。 很容易发现答案具有单调性,如果花费 xxx 的时间可以击溃目标,则花费x+1x+1x+1的时间也可以击溃目标,可以直接二分答案,考虑到二分的左右区间在 [0,1018][0,10^{18}][ 

总结：1>二分的范围基本是在1e18左右，也就是2^31次方左右.

           2>_int128 2^127~2^128

           3>改了就对了，基本是WA了32次