UVa 11136 Hoax or what (multiset or 优先队列)

/*1.822s*/

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	multiset<int> mset;
	while (scanf("%d", &n), n)
	{
		mset.clear();
		long long ans = 0;
		for (int i = 0; i < n; i++)
		{
			int k, bill, min, max;
			scanf("%d", &k);
			for (int j = 0; j < k; j++)
			{
				scanf("%d", &bill);
				mset.insert(bill);
			}
			min = *(mset.begin());
			max = *(mset.rbegin());
			ans += max - min;
			mset.erase(mset.find(max));
			///不可直接erase(max)，因为"All elements with a value equivalent to this are removed from the container."
			///也不可以erase(mset.rbegin())
			mset.erase(mset.find(min));
		}
		printf("%lld\n", ans);
	}
	return 0;
}

/*0.348s*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int unuse[1000005]; /// 记录没用过的票数

int main()
{
	int n, m, k, Min, Max;
	while (scanf("%d", &n), n)
	{
		memset(unuse, 0, sizeof unuse);
		priority_queue<int, vector<int>, greater<int> > qmin;
		priority_queue<int> qmax;
		ll ans = 0;
		while (n--)
		{
			scanf("%d", &k);
			while (k--)
			{
				scanf("%d", &m);
				++unuse[m];
				qmin.push(m), qmax.push(m);
			}
			while (unuse[qmin.top()] == 0) qmin.pop();
			Min = qmin.top();
			--unuse[Min];
			while (unuse[qmax.top()] == 0) qmax.pop();
			Max = qmax.top();
			--unuse[Max];
			ans += (ll)(Max - Min);
			qmin.pop(), qmax.pop();
		}
		printf("%lld\n", ans);
	}
	return 0;
}