当前位置:首页 > 题解目录 > 正文内容

家庭作业

亿万年的星光12个月前 (03-14)题解目录1276

题目描述

老师在开学第一天就把所有作业都布置了,每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为10,要求在6天内交,那么要想拿到这10学分,就必须在第6天结束前交。

每个作业的完成时间都是只有一天。例如,假设有7次作业的学分和完成时间如下:

作业号  1 2 3 4 5 6 7

期限      1 1 3 3 2 2 6

学分      6 7 2 1 4 5 1

最多可以获得15学分,其中一个完成作业的次序为2,6,3,1,7,5,4,注意可能d还有其他方法。

你的任务就是找到一个完成作业的顺序获得最大学分。

输入格式

第一行一个整数N,表示作业的数量。

接下来N行,每行包括两个整数,第一个整数表示作业的完成期限,第二个数表示该作业的学分。

输出格式

输出一个整数表示可以获得的最大学分。保证答案不超过longint范围。

样例输入

7
1 6
1 7
3 2
3 1
2 4
2 5
6 1

样例输出

15

提示

对于 20% 的数据,N <= 10^3;

对于 40% 的数据,N <= 10^4;

对于 60% 的数据,N <= 10^5;

对于 100% 的数据,N<= 10^6,作业的完成期限均小于 7x 10^5。


    扫描二维码推送至手机访问。

    版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

    分享给朋友:

    相关文章

    【题解】阶乘问题

    2.阶乘问题(fac.cpp)【题目描述】给定一个正整数n,求出一个最小的整数m并使得m!的末尾连续的0的个数小于n。m!=1*2*3*4*...*m【输入描述】第一行n。【输出描述】一个整数m。【样...

    【题解】踩方格

    【题目描述】有一个方格矩阵,矩阵边界在无穷远处。我们做如下假设:a、每走一步时,只能从当前方格移动一格,走到某个相邻的方格上;b、走过的格子立即塌陷无法再走第二次;c、只能向北、东、西三个方向走;请问...

    【算法】走迷宫

    【题目描述】一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜...

    【题解】最长上升子序列

    【题目描述】一个数的序列bi,当b1<b2<...<bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1,a2,...,aN),我们可以得到一些上升的子序列(ai1,ai2,...

    合影效果

    【题目描述】小云和朋友们去爬香山,为美丽的景色所陶醉,想合影留念。如果他们站成一排,男生全部在左(从拍照者的角度),并按照从矮到高的顺序从左到右排,女生全部在右,并按照从高到矮的顺序从左到右排,请问他...

    【题解】人民币问题

    【题目描述】给出任意的人民币(>10 元)的整币兑换成 5 元、2 元和 1 元币值(要求三种币值均有)的方法有多少种。【输入描述】输入任意的人民币(>10 元)的整币 100,50,20...