Wash!!(HDU_6000)
2018-10-03 17:56:34来源:博客园 阅读 ()
传送门:Wash!
题意:有n台洗衣机,m台烘干机,给出了每台机器处理意见衣服的时间,而且没见机器同时只能处理一件衣服。问如何选择机器才能使洗完衣服的时间最短。
思路:建两个优先队列,一个表示洗衣机,一个表示烘干机。每次取出最少工作时间的机器来进行洗衣,并将工作结束的时间加上处理一件衣服的时间。最后一件洗完的衣服对应着最长的结束时间,只有加上最短的烘干时间才能得到最短的结果。以此类推,倒数第二件衣服也是加上最短的烘干时间才可以得到最短时间。
贪心:前后的最长时间+最短时间得到的结果,要比从前往后最短的时间相加加到最后是最长的时间相加的结果短。
PS:注意数据范围的大小。
代码:
#include <bits/stdc++.h> using namespace std; const int maxn = 1e7+10; typedef long long ll; struct node { ll x;//工作时间 ll en;//工作到目前为止的结束时间 friend bool operator<(node a,node b) { return a.en > b.en; } } tmp; priority_queue<node> wash; priority_queue<node> dry; int l,n,m; ll a[maxn]; int main() { int T,cnt = 1; scanf("%d",&T); while(T--) { while(!wash.empty()) wash.pop(); while(!dry.empty())dry.pop(); scanf("%d%d%d",&l,&n,&m); for(int i = 0; i<n; i++) { scanf("%lld",&tmp.x); tmp.en = tmp.x; wash.push(tmp); } for(int i = 0; i<m; i++) { scanf("%lld",&tmp.x); tmp.en = tmp.x; dry.push(tmp); } for(int i = 0; i<l; i++) { tmp = wash.top();//取出最短工作时间的机器来洗衣服 a[i] = tmp.en; tmp.en += tmp.x;//结束时间加一段工作时间 wash.pop(); wash.push(tmp);//工作结束后投入等待序列 } ll ans = 0; for(int i=l-1; i>=0; i--) { tmp = dry.top(); ans = max(ans, a[i]+tmp.en);//更新洗衣服的结束时间 tmp.en += tmp.x; dry.pop(); dry.push(tmp); } printf("Case #%d: %lld\n",cnt++,ans); } return 0; } /* 样例输入: 2 1 1 1 1200 34 2 3 2 100 10 1 10 10 样例输出: Case #1: 1234 Case #2: 12 */
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:c++文件对齐
- HDU-2955-Robberies(0-1背包) 2020-03-30
- hdu1455 拼木棍(经典dfs) 2020-02-29
- anniversary party_hdu1520 2020-02-16
- hdu1062 text reverse 2020-01-27
- hdu4841 2020-01-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash