bzoj2947: [Poi2000]促销

时间:2024-08-25 23:37:14

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 178  Solved: 119
[Submit][Status][Discuss]

Description

Bytelandish连锁超市委托你编写一个程序来模拟一项即将施行的促销活动,该活动的规则如下: 
●想要参与的顾客,只需把他的个人资料写在帐单上,并把帐单放入投票箱; 
●每天活动结束时,数额最大、最小的两张帐单被取出,付款数额最大的顾客将获得一笔奖金,价值为取出的两张帐单的数额之差; 
●为了不重复计算,取出的两张帐单不再放回箱子,而剩下的帐单仍保留在箱中,进行第二天的活动。 
超市每天的营业额很大,因此可假定:每天活动结束时,箱中至少有两张帐单以供取出。 
你的任务是根据每天投入箱中的帐单,计算出这项促销活动期间超市付出的奖金总数额。 
任务: 
编写一个程序,完成下列工作: 
●读入投入箱中的帐单的信息; 
●算出促销活动期间的奖金总额;

Input

第一行是一个整数 n(1 <= n <= 5000),表示促销活动历时的天数。
以下的n行,每行包含若干由空格分隔的非负整数。第i+1行的数表示在第i天投入箱子的账单金额。每行的第一行是一个整数k(0 <= k <= 105), 表示当日账单的数目。后面的k个正整数代表这k笔账单的金额,均小于106
整个活动中涉及到的账单笔数不会超过106 。

Output

唯一一行是一个整数,等于整个促销活动中应该付出的奖金总额。

Sample Input

5
3 1 2 3
2 1 1
4 10 5 5 1
0
1 2

Sample Output

19
我的简单方法:  因为保证至少有两张,所以维护一个大根堆,维护一个小顶堆,把所有元素都压进去(两个堆里都有所有的元素),然后每次pop堆顶就是最大和最小,因为至少有两张,所以不会取到同一张。
记得刘汝佳的书上好像有这道题

bzoj2947: [Poi2000]促销