传送门

思路:

  先按学分从大到小排序,根据贪心的思想尽可能地让作业的完成时间延后,这样就能有更多空间给那些限制比较严格的作业

  设 f [ i ] 为点 i 向左的最小空闲时间

  对于一个限制 t 的作业,我们将它放在 f [ t ] 上,同时使 f [ t ] = f [ t ] - 1(表示这个时间被占用了)

  再用并查集维护一下。

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdlib>
#include<stack>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>
using namespace std;
#define lck_max(a,b) ((a)>(b)?(a):(b))
#define lck_min(a,b) ((a)<(b)?(a):(b))
typedef long long LL;
const int maxn=1e6+;
LL n,ans,maxx,fa[maxn];
struct hh
{
LL w,las;
}t[maxn];
inline LL read()
{
LL kr=,xs=;
char ls;
ls=getchar();
while(!isdigit(ls))
{
if(!(ls^))
kr=-;
ls=getchar();
}
while(isdigit(ls))
{
xs=(xs<<)+(xs<<)+(ls^);
ls=getchar();
}
return xs*kr;
}
inline void out(LL xs)
{
if(!xs) {putchar(); return;}
if(xs<) putchar('-'),xs=-xs;
int kr[],ls=;
while(xs) kr[++ls]=xs%,xs/=;
while(ls) putchar(kr[ls]+),ls--;
}
inline bool cmp(const hh&a,const hh&b)
{
return a.w>b.w;
}
inline LL find(LL u)
{
return u==fa[u]?u:fa[u]=find(fa[u]);
}
int main()
{
n=read();
for(LL i=;i<=n;i++)
t[i].las=read(),t[i].w=read(),maxx=lck_max(maxx,t[i].las);
for(LL i=;i<=maxx;i++) fa[i]=i;
sort(t+,t+n+,cmp);
for(LL i=;i<=n;i++)
{
LL lck=find(t[i].las);
if(lck)
ans+=t[i].w,fa[lck]=lck-;
}
out(ans),putchar('\n');
return ;
}

最新文章

  1. awk命令详解
  2. uva12063数位dp
  3. Javascript初学篇章_7(DOM)
  4. Low Power Consumption Design --- MCU Attention
  5. php调用一个c语言写的接口问题
  6. js处理异常try{}catch(e){}
  7. MongoVUE的使用
  8. Fragment 切换问题
  9. 解析C#中[],List,Array,ArrayList的区别及应用
  10. PHP经验——PHPDoc PHP注释的标准文档(翻译自Wiki)
  11. Linux基础(一)
  12. hdu1151 Air Raid,DAG图的最小路径覆盖
  13. Knockout获取数组元素索引的2种方法,在MVC中实现
  14. QGIS2.18.0的精简编译
  15. Chrome浏览器的使用
  16. tsc.exe 已退出 代码为 1
  17. 你对安卓触控一体机了解多少?视野还停留在windows一体机上?
  18. angular select2 ng-model 取值 ng-change调用方法
  19. curl 发送 post 请求
  20. 基于链路的OSPF简单口令认证

热门文章

  1. spring batch (二) 元数据表
  2. jenkins深入学习
  3. BIML 101 - ETL数据清洗 系列 - BIML 快速入门教程 - 序
  4. ElasticSearch 随笔
  5. PeopleSoft 单点登录
  6. ASP.NET gridview导出excel,防止繁体产生有乱码的方式
  7. 再谈javascriptjs原型与原型链及继承相关问题
  8. HttpClient 知识点
  9. 运行main方法找不到类
  10. spring boot + vue + element-ui全栈开发入门——前端编辑数据对话框