题解 | #汀博尔#
汀博尔
https://ac.nowcoder.com/acm/problem/14504
逐条分析
1.题目要求我们上交的货物必须同时满足总量S和单个限制L,如果有一棵树初始时就直接满足S、L,那就不需要等待直接取时间为0,否则就要讨论时间的取值;
2.题目要求我们求最小的等待时间(假设答案为t , t在“l~r”这个范围内),那么我们就只需要确定l和r,就可以通过二分查找得到t了。
3.由题意可知时间存在取0的情况,即l=0。我们再枚举可以让每一棵树单独满足 “S和L” 所需的时间,取其中最小值,就可以确定r了;
4.另外大家一定要注意,答案一定要同时满足 “S和L” 这两个条件 , 满足S不一定满足L;
5.注意看清题目给的数据范围! long long 接近10^18 , unsigned long long 超过10^19;
6.当然这道题也可以直接将r定义为10^18 , 但这样二分时间会变长;
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=2e6+10;
int h[N],a[N], n;
LL S ,L ,t[N];
bool check(LL mid)
{
LL sum_g=0;
for(int i=1;i<=n;i++)
if(a[i]*mid+h[i] >= L ) sum_g+=(a[i]*mid+h[i]);//
if(sum_g>=S) return true;
else return false;
}
int main()
{
LL min_t=1e18+10;
cin>>n>>S>>L;
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(h[i]<S || h[i]<L) min_t=min(min_t , ((S+L)/a[i])+1 );
else {min_t=0; break;}
}
LL l=0 , r=min_t;//
while(l<r)
{
LL mid=(l+r)>>1;
if( check(mid) ) r=mid;
else l=mid+1;
}
cout<<r<<endl;
return 0;
}