支付帐单问题

支付帐单问题

题目描述

比尔最近遇到了一件麻烦事。每天上午，他会收到若干张帐单（也可能一张也没收到）
，
每一张都有一定的面额。下午，他会从目前还没有支付的帐单中选出面额最大和最小的两
张，并把它们付清。还没有支付的帐单会被保留到下一天。现在比尔已经知道他每天收到
帐单的数量和面额，请你帮他给出支付的顺序。
输入格式

第1 行：一个正整数N(N≤30,000)，表示总共的天数。

第2 行到第N+1 行：每一行描述一天中收到的帐单。先是一个非负整数M，表示当天
收到的账单数，后跟M 个正整数（都小于1,000,000,000），表示每张帐单的面额。

输入数据保证每天都可以支付两张帐单，并且帐单会在最后一天全部付清。
输出格式

输出共N 行，每行两个用空格分隔的整数，分别表示当天支付的面额最小和最大的支
票的面额。
输入样例

4

3 3 6 5

2 8 2

3 7 1 7

0
输出样例

3 6

2 8

1 7

5 7

解：从题目给出的数据范围可以看出，可以算法的时间复杂度要比O(n2)低，O(n log n)
是可以接受的。O(n log n)的算法也有很多，比如，我们可以建立两个堆，一个最大堆，一
个最小堆，并在相应元素之间建立一个映射。收到账单时，就把面额推入两个堆中，调整
位置；支付帐单时，分别从两个堆中取出堆顶元素，并进行调整。由于元素在入堆后位置
需要进行调整，因此很难用STL 中的优先队列来实现，如果采用这种算法，我们必须自己
写堆的代码。

另外一种O(n log n)的算法就是用平衡二叉树，但如果自己写平衡二叉树的算法，实现
起来比上面一种更繁。但由于STL 中的集合是用红黑树来实现的，借助它，我们的程序可
以变得十分简单（注意到帐单的面额可能会相同，我们必须使用multiset）

#include <iostream>
#include <set>
using namespace std;
int main()
{

int n;

 cin >> n;

 multiset<int> bills;

while(n--)
{

int m;

 cin >> m;

while(m--)
{

int a;

 cin >> a;

 bills.insert(a)
;

 
}

 cout << *bills.begin() << ' ' << *--d() << endl;

 ase(bills.begin())
;

 ase(--d())
;

 
}
}