【uva 1153】Keep the Customer Satisfied(算法效率–贪心+优先队列)

【uva 1153】Keep the Customer Satisfied(算法效率–贪心+优先队列)

大家好,又见面了,我是全栈君。

题意:有N个工作,已知每个工作需要的时间和截止时间。要求所有工作穿行完成,第一项任务开始的时间不早于时刻0。问最多能完成多少个工作。(N≤800000)

解法:贪心。可以模型化题目为:已知N个任务的长度和右端点的限制位置,问最多能完成的任务的个数。——也就是每一步在一定条件下要使得数目尽量大,以及时间尽量短(最优)。
   于是可以按截止时间(这就是条件●_●)从小到大排序,先考虑截止时间早的,暂时放入选择的队列中,加入其时间。接着对于当前新的工作,若按当前选择的工作的情况无法在截止时间之前完成这个工作,分2种情况讨论:(1)当前工作需要的时间比选择的队列中工作时间最长的还要长,就放弃这个工作,使完成相同数目工作的耗时尽量小;(2)工作时间比队列中时间最长的要短,就删去队列中时间最长的任务并且将当前的工作加入队列。–“最优子结构”  这样O(n)扫一次,加上使用优先队列,时间复杂度就是O(n log n)。

P.S.不能不判断就选了第一个……

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<iostream>
 6 #include<queue>
 7 #include<vector>
 8 using namespace std;
 9 
10 const int N=(int)8e5+10;
11 int n;
12 struct node{
   
   int d,t;}a[N];
13 priority_queue<int> q;
14 
15 bool cmp(node x,node y) {
   
   return x.t<y.t;}
16 int main()
17 {
18     int T;
19     scanf("%d",&T);
20     while (T--)
21     {
22       scanf("%d",&n);
23       for (int i=1;i<=n;i++)
24         scanf("%d%d",&a[i].d,&a[i].t);
25       sort(a+1,a+1+n,cmp);
26       while (!q.empty()) q.pop();
27       int sum=0,cnt=0;
28       for (int i=1;i<=n;i++)
29       {
30         if (sum+a[i].d<=a[i].t)
31         {
32           q.push(a[i].d);
33           sum+=a[i].d, cnt++;
34         }
35         else
36         {
37           if (q.empty()) continue;//
38           int x=q.top();
39           if (a[i].d<x)
40           {
41             sum=sum-x+a[i].d;
42             q.pop(),q.push(a[i].d);
43           }
44         }
45       }
46       printf("%d\n",cnt);
47       if (T) printf("\n");
48     }
49     return 0;
50 }

 

转载于:https://www.cnblogs.com/konjak/p/6055552.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108787.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 设计模式-单例模式(Singleton)

    设计模式-单例模式(Singleton)

  • Latex插入图片却不显示问题小结

    Latex插入图片却不显示问题小结1、首先检查有没有导入宏包\usepackage{graphicx}2、检查图片路径有无问题3、可以尝试将Tex的同名文件删除,重新编译生成4、若是文章分栏\begin{multicols}{2}那是因为multicols环境不能识别figure环境,重新定义一个环境即可\newenvironment{figurehere}{\def\@captype{figure}}{}\makeatother%用于连接公式编号在文中,用figureher

  • 乌班图pycharm激活码2022年_在线激活2022.02.12

    (乌班图pycharm激活码2022年)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html4K…

  • 随机梯度下降法和批量梯度下降法_梯度下降法优化

    随机梯度下降法和批量梯度下降法_梯度下降法优化深度学习最常用的优化方法就是随机梯度下降法,但是随机梯度下降法在某些情况下会失效,这是为什么呢?带着这个问题我们接着往下看。一个经典的例子就是假设你现在在山上,为了以最快的速度下山,且视线良好,你可以看清自己的位置以及所处位置的坡度,那么沿着坡向下走,最终你会走到山底。∑i=1n∇θf(θ;xi,yi)+∇θϕ(θ)\sum_{i=1}^{n}\nabla_{\theta}f\left(\theta;x_{i},y_{i}\right)+\nabla_{\theta}\phi(\theta

  • arm linux 移植全部过程「建议收藏」

    arm linux 移植全部过程「建议收藏」armlinux移植全部过程总述功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能,丰富你的文章UML图表FLowchart流程图导出与导入导出导入总述之前做过linux在powe…

  • 简单粗暴无需拼接下载 blob (ts)视频文件

    简单粗暴无需拼接下载 blob (ts)视频文件网上很多视频采用blob来播放视频,查看源码会发现video的src为形如:src=”blob:https://*/f2880c6a-c2c5-4146-96b2-944ae555b76a”<videoid=””class=””preload=”auto”playsinline=”playsinline”webkit-playsinline=””x5-playsinl…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号