[BZOJ1572] [Usaco2009 Open]工作安排Job(贪心 + 堆)
2024-08-30 07:46:30
把任务按照d排序
一次加入到堆中,如果当前放不进堆中,并且比堆中最小的大,
就从堆中弹出一个数,再把当前的数放进去
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100001
#define LL long long using namespace std; int n;
LL ans;
priority_queue <LL, vector <LL>, greater <LL> > q; struct node
{
LL d, p;
}a[N]; inline LL read()
{
LL x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
} inline bool cmp(node x, node y)
{
return x.d < y.d;
} int main()
{
int i, now = 0;
n = read();
for(i = 1; i <= n; i++)
a[i].d = read(), a[i].p = read();
sort(a + 1, a + n + 1, cmp);
for(i = 1; i <= n; i++)
if(q.size() < a[i].d) q.push(a[i].p);
else if(!q.empty() && a[i].p > q.top())
{
q.pop();
q.push(a[i].p);
}
while(!q.empty()) ans += q.top(), q.pop();
printf("%lld\n", ans);
return 0;
}
最新文章
- 2016多校联合训练4 F - Substring 后缀数组
- 新闻类网站rss接口的编写心得
- avalonjs
- Node.js与Sails~Model数据模型
- com.android.org.bouncycastle.jce.exception.ExtCertPathValidatorException: Could not validate certificate: current time:
- [转载]SharePoint 2013搜索爬外网配置
- Erlang 的新数据结构 map 浅析
- GridControl控件的数据显示的样式控制(转)
- ModelFirst的CRUD
- WCF 已超过传入消息(65536)的最大消息大小配额。若要增加配额,请使用相应绑定元素上的 MaxReceivedMessageSize 属性
- 总结css兼容问题
- stm32f107vc在IAR环境下,引用库函数的工程文件的配置方法
- UIPickerView基本用法
- NULL指针 Void* 和野指针
- win2008 64位下.net 无法访问oracle
- js判断访问者是否来自移动端代码
- [ios2]UItableview相关 【转】
- robotium问答
- Python爬虫进阶(Scrapy框架爬虫)
- 超哥笔记 -- 用户管理、权限设置、进程管理、中文配置、计划任务和yum源配置(5)