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

家庭作业

亿万年的星光1年前 (2025-03-14)题解目录1397

题目描述

老师在开学第一天就把所有作业都布置了,每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为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。


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

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

    分享给朋友:

    相关文章

    【题解】前缀最小值

    【题目描述】求一个数列的所有前缀最小值之和。即:给出长度为n的数列a[i],求出对于所有1<=i<=n,min(a[1],a[2],...,a[i])的和。由于读入较大,数列由随机种子生成...

    【题解】变换数组

    【题目描述】输入一个数组 a,包含有 n 个元素 a1,a2,⋯,an。对这个数组进行 m 次变换,每次变换会将数组 a ...

    【题解】金银岛

    题目描述某天KID利用飞行器飞到了一个金银岛上,上面有许多珍贵的金属,KID虽然更喜欢各种宝石的艺术品,可是也不拒绝这样珍贵的金属。但是他只带着一个口袋,口袋至多只能装重量为w的物品。岛上金属有s个种...

    字符全排列

    【题目描述】给定一个由不同的小写字母组成的字符串,输出这个字符串的所有全排列。我们假设对于小写字母有‘a’ <‘b’ < … <‘y’<‘z’,而且给定的字符串中的字母已经按照...

    【题解】滚动的榜单

    【题目描述】某比赛的成绩,是依次出现的,而每个选手的成绩依次公布的时候,榜单都会刷新一遍,就能看到该选手在当前榜单加入时,所在的名次。下面给出了榜单选手的成绩,这里想知道,对于某个选手,求该选手在加入...

    【题解】愤怒的牛

    【题目描述】农夫 John 建造了一座很长的畜栏,它包括N(2<=N<100000)个隔间,这些小隔间依次编号为x1,x2,...xn(0<=xi<=1000000000)。但...