学步园

STL中priority_queue容器的应用，反正题目就是基于贪心的原则

#include <cstdio>
#include <iostream>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
// http://acm.hdu.edu.cn/showproblem.php?pid=4302
const int MAXN = 100005;
priority_queue<int> aa;
priority_queue< int, vector<int>, greater<int> > bb;
int main() 
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif
	int t, cs = 0;
	scanf("%d", &t);
	while (t--)
	{
		while (!aa.empty()) aa.pop();
		while (!bb.empty()) bb.pop();
		int L, n, x = 0, f = 1;
		scanf("%d%d", &L, &n);
		__int64 res = 0;
		while (n--)
		{
			int c, d, e = x;
			scanf("%d", &c);
			if (!c)
			{
				scanf("%d", &d);
				if (d >= x) bb.push(d);
				else aa.push(d);
			}
			else
			{
				if (!aa.empty() && !bb.empty())
				{
					c = aa.top(); d = bb.top();
					if ( (x-c)==(d-x) )
					{
						if (x != c)
						{
							if (f == 1) bb.pop(), x = d;
							else aa.pop(), x = c;
						}
						else
						{
							aa.pop();
						}
					}
					else if ( x-c > d-x)
					{
						bb.pop();
						f = 1;
						x = d;
					}
					else
					{
						aa.pop();
						f = -1;
						x = c;
					}
				}
				else if (!aa.empty())
				{
					c = aa.top();
					aa.pop();
					if (x != c) 
					{
						f = -1;
						x = c;
					}
				}
				else if (!bb.empty())
				{
					c = bb.top();
					bb.pop();
					if (x != c)
					{
						f = 1;
						x = c;
					}
				}
				res += abs(x-e);
			}
		}
		printf("Case %d: %I64d\n", ++cs, res);
	}
	
	
    return 0;
}