题解 P4058 [Code+#1]木材

前言

这什么题啊，不就是个二分答案我从65到100都经历了一遍……（瞬间气哭）

\(\sf {Solution}\)

题目理解起来不难的，大意就懒得写了。

一眼二分答案。

此题属于在形如 \(\{0,0,0....1,1,1,\}\) 的序列中查找第一个 \(1\) 的题型。

算法流程：

初始化 \(l=0,r=inf\) （ \(r\) 尽可能大）。
如果 \(l=r\) ，停止循环。
计算中点 \(mid=\left\lfloor\dfrac{l+r}{2}\right\rfloor\)。
若等待 \(mid\) 个月满足条件， \(r=mid\) 。
否则 \(l=mid+1\) 。
回到2。

至于如何判断是否满足条件，写一个函数check一下就珂以了啦~

\(\sf {P.S.}\)

什么都要开unsigned long long，否则会WA的很惨。

\(\sf {Code}\)

#include<cstdio>

using namespace std;

unsigned long long n,s,k,mid,a[200005],h[200005];

bool check(unsigned long long x)

{

	unsigned long long ans=0;

	for(unsigned long long i=1;i<=n;++i)

		if(h[i]+x*a[i]>=k)//超过要求高度的树计算在总长度范围内

			ans+=h[i]+x*a[i];

	if(ans>=s)

		return true;

	return false;//如果满足订单需求就返回true

}

int main()

{

	scanf("%lld%lld%lld",&n,&s,&k);

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

		scanf("%lld",&h[i]);

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

		scanf("%lld",&a[i]);

	unsigned long long l=0,r=10000000000000000;//l和r的初始化

	while(l<r)

	{

		mid=(l+r)/2;

		if(check(mid))

			r=mid;

		else l=mid+1;

	}//二分

	printf("%lld",l);//输出结果

	return 0;

}

巴特西

题解 P4058 [Code+#1]木材

前言

\(\sf {Solution}\)

\(\sf {P.S.}\)

\(\sf {Code}\)

最新文章

热门文章