CCF-CSP 202303-2 垦田计划

本题解法多，这里介绍用二分答案。

首先复现一下二分板子，这里只介绍该题用到的。

 该题中，minAns是每块区域的最少开垦天数。maxAns是开垦天数的最大值1e5。

接下来是check函数

考虑二分得到的答案x，在函数内统计该答案下所耗费的总资源数sum，即(每块耕地的资源-x)*投入资源数量。如果总资源数sum<=m，返回true，否则返回false。

算法总的时间复杂度为O(nlogm)

具体代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
const int INF=1e9;
typedef long long ll;
int n,k,ans,maxt;
ll m;
struct node{
	int t,c,cnt;
}a[maxn];
 
bool check(int x){
	ll sum=0;
	for(int i=1;i<=n;i++){
		sum += (max(0,a[i].t-x))*a[i].c;
	}
	if(sum <= m)return true;
	return false;
}
 
int main() {
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i].t>>a[i].c;
		maxt=max(maxt,a[i].t);
	}
	int l=k,r=1e5+5;
	while(l<=r){
		int mid=l+(r-l)/2;
		if(check(mid)){
			ans = mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	cout<<ans;
	
	return 0;
}