NC25547. 晾衣服
描述
鸡尾酒从杭州回来，囤积了许多衣服，洗好之后，他发现晾衣服是一件麻烦的事。
鸡尾酒每天都要专心卖萌，没时间管这些衣服，所以在挂好每件衣服之后就不会再调整，他只希望能最快的看到所有衣服全部被晾干。
请你帮鸡尾酒算算，假如他以最优决策挂衣服，最早经过多长时间，所有衣服都能被晾干。
如果他永远无法一次性晾干所有衣服，输出-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
C++11(clang++ 3.9) 解法, 执行用时: 403ms, 内存消耗: 4264K, 提交时间: 2020-02-26 12:36:13
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+11;
int a[maxn],b[maxn],c[maxn],d[maxn],e[maxn];
int LL=1,rr=1e9;
int n,l;
bool check(int x)
{
ll sum=0;
for(int i=0;i<n;i++)
{
if(1ll*e[i]*x>=a[i]) sum+=d[i];
else if(1ll*c[i]*x>=a[i]) sum+=b[i];
else return false;
}
return sum<=l;
}
int main()
{
int t;
cin>>n>>l;
for(int i=0;i<n;i++)
{
cin>>a[i]>>b[i]>>c[i]>>d[i]>>e[i];
}
int ans=-1;
while(LL<=rr)
{
int mid=(LL+rr)>>1;
if(check(mid))
{
rr=mid-1;
ans=mid;
}
else LL=mid+1;
}
cout<<ans<<endl;
}
C++14(g++5.4) 解法, 执行用时: 138ms, 内存消耗: 9704K, 提交时间: 2019-05-11 21:31:31
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],b[N],c[N],d[N],e[N];
int n,l;
int ans=-1;
int ll=1,rr=1e9,mid;
bool check(){
long long sum=0;
for(int i=0;i<n;i++){
if(1ll*e[i]*mid>=a[i]) sum+=d[i];
else if(1ll*c[i]*mid>=a[i]) sum+=b[i];
else return false;
}
return sum<=l;
}
int main()
{
cin>>n>>l;
for(int i=0;i<n;i++)
scanf("%d%d%d%d%d",&a[i],&b[i],&c[i],&d[i],&e[i]);
while(ll<=rr){
mid=(ll+rr)>>1;
if(check()){
rr=mid-1;
ans=mid;
}
else{
ll=mid+1;
}
}
printf("%d",ans);
return 0;
}