| 题目名称 | 755. [USACO Open09] 工作进度 | 
|---|---|
| 输入输出 | joba.in/out | 
| 难度等级 | ★ | 
| 时间限制 | 1000 ms (1 s) | 
| 内存限制 | 128 MiB | 
| 测试数据 | 12 | 
| 题目来源 | 
 | 
| 开放分组 | 全部用户 | 
| 提交状态 | |
| 分类标签 | |
| 分享题解 | 
| 通过:31, 提交:146, 通过率:21.23% | ||||
| 
 | 
100 | 0.161 s | 1.08 MiB | C++ | 
| 
 | 
100 | 0.162 s | 1.08 MiB | C++ | 
| 
 | 
100 | 0.167 s | 1.07 MiB | C++ | 
| 
 | 
100 | 0.172 s | 1.84 MiB | C++ | 
| 
 | 
100 | 0.182 s | 6.49 MiB | C++ | 
| 
 | 
100 | 0.185 s | 6.49 MiB | C++ | 
| 
 | 
100 | 0.186 s | 6.49 MiB | C++ | 
| 
 | 
100 | 0.212 s | 1.41 MiB | C++ | 
| 
 | 
100 | 0.223 s | 2.60 MiB | C++ | 
| 
 | 
100 | 0.224 s | 1.83 MiB | C++ | 
| 本题关联比赛 | |||
| 20120413 | |||
| 关于 工作进度 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
| 
 
另类贪 
 | ||||
| 
 
%%% 
2016-08-15 21:42
1楼
 
 | ||||
	农夫约翰总是有干不完的活!为了使牧场更高效地运转,他必须要从他的这些工作中牟利才行。他的每一个工作都只占用一个单位的时间。
他的工作日从时间0开始,一共有1,000,000,000 个单位的时间。他当前可以从N(1 <= N <= 100,000)个工作中任选一个,这N个工作编号为1~N。由于在每个单位时间内他只能做一个工作,每项工作有一个时间期限,所以他可能无法完成所有的N项工作。
第i项工作的时间期限为D_i(1 <= D_i <= 1,000,000,000),如果他在这个时间期限之前完成的话,可以获得P_i(1 <= P_i <= 1,000,000,000)的收益。
给定一个工作列表,包括时间期限,请确定约翰能获得的最大收益。注意:答案可能无法用一个32位二进制整数表示。
	输入格式:
第1行,一个整数N;
第2~N+1行,第i+1行有两个空格隔开的整数:D_i,P_i;
	输出格式:
一行,一个数,即FJ能获得的最大收益。
	输入输出样例:
joba.in
3
2 10
1 5
1 7
	joba.out
17
	输出样例解释:
先在时间1完成3号工作,再在时间2完成1号工作,最大收益为7+10=17。