这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。
题目地址：
http://acm.hdu.edu.cn/showproblem.php?pid=1050
又是一道贪心题，不过和 HDOJ 1009，HDOJ 2037不一样，这里是以局部最优反映了整体最优。
而其余2题是逐步求最优，不知道说清楚没，做了这三题就可以感觉出来了，这三题都是很经典的题目。
这题看见有人用类似上面2题的方法做了，我没去尝试，看见杭电的PPT里有更简单的方法，尝试了，写出来的代码简单易懂。
思路：首先要知道，最长的时间就是一个过道被经过的最大次数，这样题目就简单多了，求过道重复次数最大值，这里注意1，2和3，4等都是对门的，要采用减一后除以2的方法映射到同一坐标轴上。
#include
#include
using namespace std;
// Author: Tanky Woo
// HDOJ 1050
// 0MS 180K 748B
int T, N;
int possible[201];
// www.wutianqi.com
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d", &T;);
int s, t;
while(T--)
{
memset(possible, 0, sizeof(possible));
scanf("%d", &N;);
for(int i = 0; i < N; ++i)
{
scanf("%d %d", &s;, &t;);
// 注意这里不是简单的s到t，因为1,2是相对的。
// 所以，减一后除以2可以把1，2；3，4等对应到同一坐标轴上.
s = (s-1)/2;
t = (t-1)/2;
if(s > t)
{
s += t;
t = s-t;
s -=t;
}
for(int j = s; j <= t; ++j)
possible[j]++;
}
int max_sum = -1;
// 不知道这算不算局部最优求正题最优，个人觉得是这样的吧
for(int i = 0; i < 201; ++i) //求出哪块区域最大，也就是占用时间最长
if(possible[i] > max_sum)
max_sum = possible[i];
printf("%d\n", max_sum*10);
}
return 0;
}