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

家庭作业

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

题目描述

老师在开学第一天就把所有作业都布置了,每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为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个放核物质的坑,坑排列在一条直线上。如果连续3个坑中放入核物质,则会发生爆炸,于是,在某些坑中可能不放核物质。现在,请你计算:对于给定的N,求不发生爆炸的放置核物质的方案总数...

【题解】公交乘车

【题解】公交乘车

【题目描述】A城市有一条非常特别的街道,该街道在每个公里的节点上都有一个公交车站,乘客可以在任意的公交站点上车,在任意的公交站点下车。乘客根据每次乘坐公交的公里数进行付费,比如,下表就是乘客乘坐不同的...

【题解】阳光

【题目描述】给出一个n*n的矩阵,矩阵每个元素数值代表这个位置的阳光情况,给出正整数k,需要我们求出哪一处的k*k 区域的阳光平均值最多,阳光平均值为k*k 区域的阳光总和除于k*k。蒜头君想让我们输...

【题解】01背包

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

【题解】运动员和训练师的最大匹配数

【题目描述】给你一个下标从 0 开始的整数数组 players ,其中 players[i] 表示第 i 名运动员的&n...

【题解】使每位学生都有座位的最少移动次数

【题目描述】一个房间里有 n 个 空闲 座位和 n 名 站着的 学生,房间用一个数轴表示。给你一个长度为 n&...