Work Scheduling G
提交数: 3, 通过率: 66.67%, 平均分: 66.67
题目描述:
约翰有太多的工作要做。为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。他的工作日从 \( 0 \) 时刻开始，有 \( 10^9 \) 个单位时间。在任一时刻，他都可以选择编号1到N的N ( \( 1 \le N \le 10^5 \) )项作中的任意一项工作来完成。 因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有N个工作，虽然还是有可能。对于第个工作，有一个截止时间 \( D_i \) ( \( 1 \le D \le 10^9 \) )，如果他可以完成这个工作，那么他可以获利 \( P_i \) ( \( 1 \le P \le 10^9 \) 在给定的工作利润和截止时间下，约翰能够获得的利润最大为多少？
在给定的工作利润和截止时间下，约翰能够获得的利润最大为多少呢? 答案可能会超过32位整型.
输入格式:
第1行：一个整数N。
第2到N + 1行： 第 i + 1行有两个用空格分开的整数 \( D_i \) 和 \( P_i \) 。
输出格式:
输出一行，有一个整数，表示最大的获利值。
样例输入:
3 2 10 1 5 1 7
样例输出:
17
提示:
样例说明
第1个单位时间完成第3个工作( 1, 7 ) ，然后在第2个单位时间完成第1个工作 ( 2 , 10 ) 以达到最大利润。
空间限制: 64MB
来源: Usaco2009 Open Gold