题解 | #汀博尔#

汀博尔

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;	
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
11-27 10:52
点赞 评论 收藏
分享
10-16 09:58
已编辑
门头沟学院 Java
点赞 评论 收藏
分享
找不到工作死了算了:没事的,雨英,hr肯主动告知结果已经超越大部分hr了
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务