2018.10.27 loj#6035. 「雅礼集训 2017 Day4」洗衣服(贪心+堆)
程序员文章站
2024-03-13 23:00:52
...
传送门
显然的贪心题啊。。。考试没调出来10pts滚了妙的一啊
直接分别用堆贪心出洗完第件衣服需要的最少时间和晾完第件衣服需要的最少时间。
我们设第一个算出来的数组是,第二个是,然后令数组是的一个任意排列。
于是要求{{}}
里面东西跟排序不等式很像啊 ,于是正序倒序加起来取最大值就行了。
代码:
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=1e6+5;
int L,n,m;
typedef long long ll;
ll a[N],b[N],t1[N],t2[N],ans=0;
int main(){
L=read(),n=read(),m=read();
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >q1,q2;
for(int i=1,v;i<=n;++i)q1.push(make_pair(v=read(),v));
for(int i=1,v;i<=m;++i)q2.push(make_pair(v=read(),v));
for(int i=1;i<=L;++i){
pair<ll,ll>tmp=q1.top();
q1.pop();
t1[i]=tmp.first,tmp.first+=tmp.second,q1.push(tmp);
tmp=q2.top();
q2.pop();
t2[i]=tmp.first,tmp.first+=tmp.second,q2.push(tmp);
}
for(int i=1;i<=L;++i)ans=max(ans,t1[i]+t2[L-i+1]);
cout<<ans;
return 0;
}
上一篇: 数列极差【贪心】