hdu 1050 最大重叠数（贪心）

原题地址：

点击打开链接

题目大意：在走廊间移动椅子，每次只能移动一个，无论在任何两个房间之间移动都要花费10min，求移动所有椅子所用掉的最短时间。

解析：这题基本是求一个最大重叠数的问题，当然用贪心也可以解决。

/*
	Name: hdu 1050 
	Copyright: 
	Author: 
	Date: 15/2/21 22:28
	Description:实质为求走廊的最大重叠数 
*/

#include<cstdio>
#include<iostream>
using namespace std;

int main()
{
//	freopen("E:\input.txt", "r", stdin);
	int room[205];
	int t;
	scanf("%d", &t);
	int max;
	int a, b;
	int n;
	int i, j;
	while (t--)
	{
		max = 0;
		memset(room, 0, sizeof(room));  //每次都要重新清零
		scanf("%d", &n);
		for (i = 0; i < n; i++)
		{
			scanf("%d%d", &a, &b);
			a = (a - 1) / 2;   //由于1.3 和 2.4 其实经过的是一条走廊
			b = (b - 1) / 2;
			if (a > b)
			{
				a = a ^ b;
				b = a ^ b;
				a = a ^ b;
			}
			for (j = a; j <= b; j++)
			{
				room[j]++;
				if (room[j] > max)  //求最大的走廊的最大重叠数 
				{
					max = room[j];
				}
			}
		}
		printf("%d\n", max * 10);
	}
	return 0;
}
           

这里的几篇博客关于此题有很好的解释：

http://blog.csdn.net/code_pang/article/details/8251240

http://blog.csdn.net/niushuai666/article/details/7010417