描述
你现在要洗 l 件衣服。你有 n 台洗衣机和 m 台烘干机。由于你的机器非常的小,因此你每次只能洗涤(烘干)一件衣服。
第 i台洗衣机洗一件衣服需要 wi 分钟,第 i 台烘干机烘干一件衣服需要 di 分钟。
请问把所有衣服洗干净并烘干,最少需要多少时间?假设衣服在机器间转移不需要时间,并且洗完的衣服可以过一会再烘干。
输入
输入文件的第一行三个整数 l 、n 和 m
第二行 n 个整数 wi
第三行 m 个整数 di
输出
一行一个整数,表示所需的最少时间。
样例输入 1
1 1 1
1200
34
样例输入 22 3 2
100 10 1
10 10
样例输出
样例输出 1
1234样例输出 212
提示
数据范围
对于 10% 的数据,l=1;
对于另外 20% 的数据,l,n,m≤10
对于另外 30% 的数据,
l≤1000,n,m≤100
对于 100%的数据,
l≤10^6, n,m≤10^5
这也是个结论题结果没想出来
还瞎写了个二分结果判断挂了简单来说结论就是这样的
设有两个有序实数组:a1≤a2≤a3…≤an,b1≤b2≤…≤bn
c1,c2,…,cn是B数组的任意排列
顺序和:a1b1+a2b2+…+anbn
反序和:a1bn+a2bn−1+…+anb1
乱序和:a1c1+a2c2+…+ancn
排序不等式:反序和≤乱序和≤顺序和,当且仅当a1=a2=…=an或b1=b2=…=bn时,反序和=顺序和
这其实很好证明
考虑对于升序排序后相邻的两排上的两个点,
显然有而对于和显然最大值会小一点
那么对于显然最大值会同样更小一点
数学归纳法就可以证明倒序一定是最优的那么
我们分别求出w最优的l个时间和d最优的l个时间
倒序相加
求最大的那个就是了
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
char ch=getchar();
int res=0;
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
return res;
}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >qa;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >qb;
int n,m,l,w[100005],d[100005];
int ans1[1000005],ans2[1000005],tot;
inline bool comp(int x,int y){
return x>y;
}
signed main(){
l=read();n=read(),m=read();
for(int i=1;i<=n;i++){
w[i]=read();
qa.push(make_pair(w[i],i));
}
for(int i=1;i<=m;i++){
d[i]=read();
qb.push(make_pair(d[i],i));
}
for(int i=1;i<=l;i++){
pair<int,int> c=qa.top();qa.pop();
ans1[i]=c.first;
c.first+=w[c.second];
qa.push(c);
}
for(int i=1;i<=l;i++){
pair<int,int> c=qb.top();qb.pop();
ans2[i]=c.first;
c.first+=d[c.second];
qb.push(c);
}
sort(ans1+1,ans1+l+1);
sort(ans2+1,ans2+1+l,comp);
for(int i=1;i<=l;i++){
tot=max(tot,ans1[i]+ans2[i]);
}
cout<<tot;
return 0;
}