BZOJ 1572: [Usaco2009 Open]工作安排Job 贪心 + 堆 + 反悔
2024-09-04 04:06:48
Description
Farmer John想修理牧场栅栏的某些小段。为此,他需要N(1<=N<=20,000)块特定长度的木板,第i块木板的长度为Li(1<=Li<=50,000)。然后,FJ去买了一块很长的木板,它的长度正好等于所有需要的木板的长度和。接下来的工作,当然是把它锯成需要的长度。FJ忽略所有切割时的损失——你也应当忽略它。 FJ郁闷地发现,他并没有锯子来把这块长木板锯开。于是他把这块长木板带到了Farmer Don的农场,想向FD借用锯子。 作为一个有商业头脑的资本家,Farmer Don没有把锯子借给FJ,而是决定帮FJ锯好所有木板,当然FJ得为此付出一笔钱。锯开一块木板的费用,正比于木板的长度。如果这块木板的长度是21,那么锯开它的花费便是21美分。 谈妥条件后,FD让FJ决定切割木板的顺序,以及每次切割的位置。请你帮FJ写一个程序,计算为了锯出他想要的木板,他最少要花多少钱。很显然,按不同的切割顺序来切开木板,FJ的总花费可能不同,因为不同的切割顺序,会产生不同的中间结果。
Input
* 第1行: 一个正整数N,表示FJ需要木板的总数
* 第2..N+1行: 每行包含一个整数,为FJ需要的某块木板的长度
Output
* 第1行: 输出一个整数,即FJ完成对木板的N-1次切割的最小花费
题解:优先处理结束时间更小的. 考虑当前枚举到第 $i$ 个任务,如果可以加入,则直接处理. 如果没有处理当前任务的空间,则反悔 : (当前比最小价值大)弹出价值最小的,并加入当前任务. 小根堆维护一下即可.
#include<bits/stdc++.h>
#define setIO(s) freopen(s".in","r",stdin)
#define maxn 2000000
#define ll long long
using namespace std;
priority_queue< ll , vector<ll>, greater<ll> >Q;
struct Node
{
ll val,tim;
}key[maxn];
bool cmp(Node a,Node b)
{
return a.tim < b.tim;
}
int main()
{
// setIO("input");
ll ans=0;
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%lld%lld",&key[i].tim,&key[i].val);
}
sort(key+1,key+1+n,cmp);
for(int i=1;i<=n;++i)
{
if(key[i].tim <= (ll)Q.size())
{
if(key[i].val > Q.top())
{
ans -= Q.top();
ans += key[i].val;
Q.pop();
Q.push(key[i].val);
}
}
else
{
ans += key[i].val;
Q.push(key[i].val);
}
}
printf("%lld\n",ans);
return 0;
}
最新文章
- VMware安装Elementary OS 后不能上网问题解决方法
- noip模拟赛(10.4) 序列(sequence)
- PowerDesigner V16.5 安装文件 及 破解文件
- React和ES6(二)ES6的类和ES7的property initializer
- [OpenCV] Image Processing - Grayscale Transform
- html,xhtml和xml
- 慕课网-安卓工程师初养成-4-6 Java条件语句之 switch
- centos 6.5 minimal 安装及vm-tools安装
- selenium python (八)定位frame中的对象
- JavaScript创建对象的写法
- C#实现网络传输数据加密
- SVG 教程
- Redis 的性能幻想与残酷现实(转)
- AFNetWorking POST Multi-Part Request 上传图片
- matlab 向量法建数组(推荐)
- Davinci DM6446开发攻略——u-boot-1.3.4移植(1)
- wxPython制作跑monkey工具(python3)-带事件百分比显示界面
- openssl - 怎么打开POD格式的帮助文件
- VS中ReportView的坑爹问题
- 查看自己电脑外网IP
热门文章
- [bzoj2802][Poi2012]Warehouse Store_贪心_堆
- propagation属性的7个传播行为
- mongodb之存储引擎
- [RxJS] Get current value out of Subject (BehaviorSubject)
- Think in ISP(image sensor pipe )之How to implement an effecitive AE
- poj 2931 Building a Space Station &;lt;克鲁斯卡尔&;gt;
- FileZilla Client 免费又好用的ftp工具
- 电脑升级win10后visio的问题
- PHPExcel 使用心得
- python3用list实现栈