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

家庭作业

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

题目描述

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


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

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

    分享给朋友:

    相关文章

    【题解】01背包

    【题目描述】一个旅行者有一个最多能装 M 公斤的背包,现在有 n 件物品,它们的重量分别是W1,W2,...,Wn,它们的价值分别为C1,C2,...,Cn,求旅行者能获得最大总价值。【输入描述】第一...

    【题解】游览动物园

    【题目描述】动物园有很多游览区,小红已经在动物园的一个游览区游览,突然接到电话,要半个小时内到动物园外面跟一个朋友见面。半个小时小红只够游览完当前区域之后,游览一个最近的景区。已知从一个游览区域只能沿...

    【题解】分发饼干

    【题目描述】假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;...

    【题解】求逆序对个数

    【题目描述】有一实数序列A[1]、A[2] 、A[3] 、……A[n-1] 、A[n] (n<10000),若i<j,并且A[i]>A[j],则称A[i]与A[j]构成了一个逆序对,...

    【题解】切比雪夫距离

    【题目描述】小C有一个平面!它发现了平面上的两个点,请你求出求它们之间的切比雪夫距离。切比雪夫距离定义为x与y方向坐标差的绝对值较大值。【输入描述】四个整数,a,b,c,d。坐标为(a,b)与(c,d...

    2021年市南区程序设计竞赛(小学组)

    1.建设病房(build.cpp)【题目描述】2020年1月23日下午,武汉市建设局紧急召集中建三局等单位举行专题会议,要求参照2003年抗击非典期间北京小汤山医院模式,在武汉职工疗养院建设火神山医院...