p1093 [noip2007 普及组] 奖学金

题目描述：

某校有n个学生，编号为1~n，每个学生有ai个不同的奖学金，现在要将这些奖学金分给这n个学生。规定编号为i的学生最多只能得到bi个奖学金，同时规定相同奖学金的奖学金数量也不能超过ci个。问最多能分出多少个奖学金。

输入格式：

第一行包含一个整数n。

接下来n行，每行包含三个整数ai，bi，ci。

输出格式：

一个整数，表示最多能分出的奖学金数量。

输入样例：

5
5 2 2
3 3 1
3 2 1
4 3 3
5 5 3

输出样例：

6

算法1

(贪心) $O(nlogn)$

首先按照奖学金数量从大到小排序，然后从大到小依次分配奖学金，直到某个学生分配满了或者某个奖学金数量已经分配完了。

时间复杂度

排序的时间复杂度为O(nlogn)，分配奖学金的时间复杂度为O(n)，因此总时间复杂度为O(nlogn)。

C++ 代码

算法2

(贪心) $O(nlogn)$

首先按照奖学金数量从大到小排序，然后从大到小依次分配奖学金，直到某个学生分配满了或者某个奖学金数量已经分配完了。

时间复杂度

排序的时间复杂度为O(nlogn)，分配奖学金的时间复杂度为O(n)，因此总时间复杂度为O(nlogn)。

C++ 代码