AcWing 5017. 垦田计划
原题链接
简单
作者:
っっ
,
2024-03-17 20:28:31
,
所有人可见
,
阅读 7
// 二分枚举 消耗资源 <= m时的 最小天数
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,k;
const int N = 1E5+10;
int t[N],c[N];
int mmax = 0;
bool check(int x)
{
int cnt = 0;
for(int i = 1; i <= n;i++)
{
if(t[i] <= x) continue;
cnt += (t[i]-x)*c[i];
}
if(cnt <= m) return true;
else return false;
}
int main(){
cin >> n >> m >> k;
for(int i = 1; i <= n;i++)
{
scanf("%d%d",&t[i],&c[i]);
mmax = max(mmax,t[i]);
}
int l = k, r = mmax;
while(l < r)
{
int mid = l+r >> 1;
if(check(mid))
{
r = mid;
}
else l = mid+1;
}
cout << l;
return 0;
}