洛谷【P1873】砍树

我对二分的理解：https://www.cnblogs.com/AKMer/p/9737477.html

题目传送门：https://www.luogu.org/problemnew/show/P1873

我们可以二分高度\(high\)。显然对于能砍出\(m\)米木材的\(high\)，任何小于\(high\)的高度都不会更优（因为米尔科只需要\(m\)米木材并且他十分关注生态保护）。那么\([1,high]\)这个区间就不是备选答案区间了，我们就应该到\([high,mx]\)里去找尽可能高的\(high\)，使得当伐木机锯片在\(high\)米时可以砍下大于等于\(m\)的木材，而在\(high+1\)时必然小于\(m\)。

时间复杂度：\(O(nloga)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=1e6+5;

int a[maxn];

int n,mn,mx,m,ans;

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

bool check(int high) {

	long long res=0;

	for(int i=1;i<=n;i++)

		if(a[i]>high)res+=a[i]-high;

	return res>=m;//计算high这个高度可以砍下多少木材并且判断是否满足要求

}

int main() {

	n=read(),m=read();mn=1,mx=-1e9;

	for(int i=1;i<=n;i++)

		a[i]=read(),mx=max(mx,a[i]);

	int l=mn,r=mx;

	while(l<=r) {

		int mid=(l+r)>>1;

		if(check(mid))ans=mid,l=mid+1;

		else r=mid-1;//根据上述思路二分

	}printf("%d\n",ans);

	return 0;

}

巴特西

洛谷【P1873】砍树

最新文章

热门文章