中山纪念中学20170310洗衣服(贪心,优先队列升序【pair】)
#include<bits/stdc++.h>
using namespace std;
typedef pair<long long,int>clot;
priority_queue<clot,vector<clot>,greater<clot> >wash,dry;//升序队列
int l,n,m;
long long ans=0;
long long tim[1000010],w[100010],d[100010];//tim记录衣服的经过从洗衣机到烘干机拿出的时间之和,最晚放进烘干机那批衣服里时间之和最长的即为ans
int main()
{
scanf("%d%d%d",&l,&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld",&w[i]);
wash.push(clot(w[i],i));//将洗衣机的数据放入优先队列
}
for(int i=1;i<=m;i++)
{
scanf("%lld",&d[i]);
dry.push(clot(d[i],i));//将烘干机的数据放入优先队列
}
for(int i=0;i<l;i++)
{
clot tmp=wash.top();//取工作最快的洗衣机
wash.pop();
tim[i]=tmp.first;//当前已经工作完成的最快的洗衣机
tmp.first+=w[tmp.second];//记录时间累加,这台洗衣机累计的工作时间
wash.push(tmp);//再次放入队列让它工作
}
for(int i=l-1;i>=0;i--)//最晚洗完的衣服放到最快的烘干机里,否则会很慢,此处贪心
{
clot tmp=dry.top();//取工作最快的烘干机
dry.pop();
tim[i]+=tmp.first;//当前已经工作完成的最快的烘干机
tmp.first+=d[tmp.second];//记录时间累加,这台烘干机累计的工作时间
dry.push(tmp);//再次放入队列让它工作
ans=max(ans,tim[i]);//取一个花费时间最长的,木桶效应,有的衣服可能洗完得早放进了工作时间长的烘干机里导致时间之和更长
}
printf("%lld\n",ans);
return 0;
}
最新文章
- Python 下载网络mp4视频资源
- 图片采用base64压缩,可以以字符串的形式传送base64给服务端转存为图片
- ButterKnife的原理简述
- T138
- JavaWeb学习笔记——开发动态WEB资源(三)显示当前时间
- youtube不显示其他人头像
- Farming
- 2015年最棒的10个 JavaScript 框架
- Install TightVNC Server in RHEL/CentOS and Fedora to Access Remote Desktops
- c# 初识WPF
- Android应用程序如何使用Internet资源?
- Linux squid代理
- Elasticsearch实践(三):Mapping
- 深入理解 Servelt
- 解决CEF中显示Flash动画弹出安全警告问题
- linux驱动编写之进程独占驱动
- MVC缺点总结
- php安装后,再添加模块pdo_mysql,mysqli
- 一个struts2程序
- PHP概率,抽奖