hdu 1050Moving Tables（uvaoj 2326）

hdu 1050Moving Tables

给定一个房间的图，和从某个房间移动到某个房间的顺序，看看最少时间才能移动完成桌子。每个房间前边的空地是不能同时有两个移动占据的。我们把房间的编号映射到门前的空地即：(n+1)/2，门前的空地就被1到200编号，空地中的最大使用次数就是移动桌子的最大次数，可以用反证法证明。 代码如下：

/*************************************************************************
	> File Name: 2326.cpp
	> Author: gwq
	> Mail: [email protected] 
	> Created Time: 2014年10月10日 星期五 16时33分51秒
 ************************************************************************/

#include <cmath>
#include <ctime>
#include <cctype>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>

#define INF (INT_MAX / 10)
#define SQR(x) ((x) * (x))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repf(i, a, b) for (int i = (a); i <= (b); ++i)
#define repd(i, a, b) for (int i = (a); i >= (b); --i)
#define clr(arr, val) memset(arr, val, sizeof(arr))
#define pb push_back
#define sz(a) ((int)(a).size())
#define middle(x, y) ((x + y) >> 1)

using namespace std;
typedef set<int> si;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef long long ll;

typedef struct Node {
	int l, r;
}Node;

#define N 210

int n, vis[N];

int main(int argc, char *argv[])
{
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		clr(vis, 0);
		for (int i = 0; i < n; ++i) {
			int l, r;
			scanf("%d%d", &l, &r);

			//将每个房间门前的空地映射到1到200
			//这个空地不能同时被占用
			l = (l + 1) >> 1;
			r = (r + 1) >> 1;
			if (l > r) {
				swap(l, r);
			}
			//记录每个门前空地使用的次数，最大的使用次数
			//乘以10就是最长的移动时间，因为不可能有比这
			//使用次数多的地方了
			for (int j = l; j <= r; ++j) {
				vis[j]++;
			}
		}

		int mx = 0;
		for (int i = 1; i <= 200; ++i) {
			mx = max(mx, vis[i]);
		}

		printf("%d\n", mx * 10);
	}

	return 0;
}