牛客网——晾衣服（二分）

链接：https://ac.nowcoder.com/acm/contest/892/C
来源：牛客网
 

题目描述

鸡尾酒从杭州回来，囤积了许多衣服，洗好之后，他发现晾衣服是一件麻烦的事。

晾衣绳的长度只有L，而鸡尾酒有N件衣服，每件衣服挂在衣架上之后可以横着晾或者竖着晾，横着晾比较占晾衣绳的地方，但是受光面积大，干得也快，竖着晾反之。

鸡尾酒每天都要专心卖萌，没时间管这些衣服，所以在挂好每件衣服之后就不会再调整，他只希望能最快的看到所有衣服全部被晾干。

请你帮鸡尾酒算算，假如他以最优决策挂衣服，最早经过多长时间，所有衣服都能被晾干。

如果他永远无法一次性晾干所有衣服，输出-1。

 

输入描述:

第一行给出N,L
(1≤N≤2e5, 1≤L≤1e9)

接下来N行描述衣服，每行五个数字，分别代表湿度a，横放占晾衣架的长度b，横放每分钟减少的湿度c，竖放长度d，竖放每分钟减少的湿度e（b>d,c>e,1≤a,b,c,d,e≤1e9）

输出描述:

输出一行一个整数代表答案。

示例1

输入

2 10
100 10 100 1 1
10 3 5 2 3

输出

100

二分查找满足条件的最小时间

#include<iostream>
using namespace std;
struct node {
	int length1;
	int length2;
	int time1;
	int time2;
}p[200005];
int n,k;
bool check(int mid){//mid满足条件 
	long long sum=0;//！！！！！！！！！！ 
	for(int i=1;i<=n;i++){
		if(mid>=p[i].time1 &&mid>=p[i].time2 )
		    sum+=min(p[i].length1 ,p[i].length2 );
		else if(mid>=p[i].time1 )
		    sum+=p[i].length1 ;
		else if(mid>=p[i].time2 )
		    sum+=p[i].length2 ;
		else
		    return false;
	}
	if(sum<=k)
	    return true;
	else
	    return false;
}
int main(){
	scanf("%d%d",&n,&k);
	long long count=0;//!!!!!!!long long 
	for(int i=1;i<=n;i++){
		int num,a1,b1,a2,b2;
		scanf("%d%d%d%d%d",&num,&a1,&b1,&a2,&b2);
		count+=min(a1,a2);
		p[i].length1 =a1;
		p[i].time1 =num/b1;
		if(num%b1!=0)
		    p[i].time1 ++;
		p[i].length2 =a2;
		p[i].time2 =num/b2;
		if(num%b2!=0)
		    p[i].time2 ++;
	}
	if(count>k){
		printf("-1\n");
		return 0;
	}
	int ans,l=1,r=1e9;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}
		else
		    l=mid+1;
	}
	printf("%d\n",ans);
	return 0;
}