当前位置：网站首页>2022河南萌新联赛第（三）场：河南大学 A - 玉米大炮

2022河南萌新联赛第（三）场：河南大学 A - 玉米大炮

2022-07-26 04:29:00 【WA_自动机】

A - 玉米大炮

很容易发现答案具有单调性, 如果花费 x 的时间可以击溃目标, 则花费 x + 1 x + 1 x+1 的时间也可以击溃目标, 可以直接二分答案, 考虑到二分的左右区间在 [ 0 , 1 0 18 ] [0, 10^{18}] [0,1018], 对于 C + + 选手可能需要使用__int128 , 或者在二分的过程提前判断是否合法。

  • 时间复杂度 O ( n × l o g ( 1 0 18 ) ) O(n × log(10^{18})) O(n×log(1018))
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 100010;

int a[N],b[N];
int n,m;

int check(LL x)
{
    
	LL sum=0;
	for(int i=1;i<=n;i++)
	{
    
		sum+=(x/b[i]+1)*a[i];
		if(sum>=m) return 1;
	}
	return 0;
}

int main()
{
    
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
	LL l=0,r=1e18;
	while(l<r)
	{
    
		LL mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	cout<<r<<endl;
	return 0;
}
原网站

版权声明
本文为[WA_自动机]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_52792570/article/details/125980718

边栏推荐

猜你喜欢

随机推荐