牛客练习赛 小A与任务 解题报告
2024-10-13 08:49:49
小A与任务
链接:
https://ac.nowcoder.com/acm/contest/369/B
来源:牛客网
题目描述
小A手头有 \(n\) 份任务,他可以以任意顺序完成这些任务,只有完成当前的任务后,他才能做下一个任务
第 \(i\) 个任务需要花费 \(x_i\) 的时间,同时完成第 \(i\) 个任务的时间不能晚于\(y_i\) ,时间掌控者向小A提出了一个条件:如果完成第 \(i\) 个任务的时间本应是 \(t\) ,但小A支付 \(m\) 个金币的话,他可以帮助小A在$ t−m×z_i$ 时刻完成第 \(i\) 个任务, \(z_i\) 是时间参数,会在输入中给出
小A想按时完成所有任务,请你帮他制定一个花费金币最少的方案
注意:不能使得某个任务的花费时间小于 0 ,花费的金币可以不是整数
输入描述:
第一行一个整数 \(n\) ,表示小A的任务数量
接下来\(n\)行,每行三个整数,分别表示 \(z_i,x_i,y_i\)
输出描述:
一行一个实数,表示小A最少需要花费的金币数,四舍五入保留一位小数
备注:
\(1≤n≤2×10^5\)
\(1≤x_i,z_i≤3×10^3\)
\(1≤y_i≤10^5\)
日常做不出沙比题,哎,没救了
这种看起来可以贪心搞一搞的应该很容易看出来可以拿堆延迟操作的...
首先按\(y\)定操作顺序
然后把二元组\((res,cos)\)即任务\(i\)和它剩余可以买的时间丢到堆里,维护一个当前时间戳,当时间不够用时,在堆里买就行了,没用完的任务记得放回堆就可以了
Code:
#include <cstdio>
#include <queue>
#include <algorithm>
const int N=2e5+10;
#define yuucute 233
struct node
{
int z,x,y;
bool friend operator <(node a,node b){return a.y<b.y;}
}bee[N];
#define mp(a,b) std::make_pair(a,b)
std::priority_queue <std::pair<int,int> > q;
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&bee[i].z,&bee[i].x,&bee[i].y);
std::sort(bee+1,bee+1+n);
int tim=0;double ans=0;
for(int i=1;i<=n;i++)
{
q.push(mp(bee[i].z,bee[i].x));
int res=bee[i].y-tim;
if(res<bee[i].x)
{
bee[i].x-=res;
while(yuucute)
{
int re=q.top().second,cos=q.top().first;
q.pop();
if(bee[i].x>re)
{
bee[i].x-=re;
ans+=1.0*re/(1.0*cos);
}
else
{
ans+=1.0*bee[i].x/(1.0*cos);
re-=bee[i].x;
q.push(mp(cos,re));
break;
}
}
tim=bee[i].y;
}
else tim+=bee[i].x;
}
printf("%.1lf\n",ans);
return 0;
}
2019.2.15
最新文章
- SpringMVC与MyBatis整合之日期格式转换
- centos 6.5 X64 安装 mongodb 2.6.1 (笔记 实测)
- C#网络编程基础知识
- Rabbitmq实现负载均衡与消息持久化
- outlook无法创建保存附件解决
- socket 中午吃的啥
- RPGJS 进阶分析之 如何使用RMXP导出的数据
- ACM——数的计数
- java 键盘输入多种方法 .(转载)
- 第22章 职责链模式(Chain of Responsibility)
- cli/php.ini和fpm/php.ini的区别
- Linux常用网络测试命令
- XMPP(一)-openfire服务端的安装和搭建
- 爬虫之selenium和PhantomJS
- Python中的几种矩阵乘法(转)
- TCP连接的TIME_WAIT过多导致 Tomcat 假死
- Ubuntu 14.04 安装adobe flash player
- 0x01 现阶段目标
- Uncaught (in promise) Provided element is not within a Document
- Linux 设置 LD_LIBRARY_PATH