学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1050

题目大意：

和活动安排相似的一道题，贪心就可以了。但是自己wrong了半个小时，也不知道哪里错了。。。悲剧。

之后用另外的思路写出来了，就是求走廊的最大重叠数，因为房间是对称分布的，需要注意一下奇偶的情况。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 210
int a[N];

struct node
{
	int s, t;
}p[N];

bool cmp(const node &a, const node &b)
{
	return a.s < b.s;
}

int main()
{
	int ncase;
	int num;
	int max;
	scanf("%d", &ncase);
	while(ncase--)
	{
		max = -1;
		memset(a, 0, sizeof(a));
		scanf("%d", &num);
		for(int i = 0; i < num; ++i)
		{
			scanf("%d%d", &p[i].s, &p[i].t);
			p[i].s = (p[i].s + 1) / 2; //处理奇偶情况
			p[i].t = (p[i].t + 1) / 2;
			if(p[i].s > p[i].t)
				swap(p[i].s, p[i].t);
			for(int j = p[i].s; j <= p[i].t; ++j)
			{
				a[j]++; //走廊覆盖
				if(max < a[j])
					max = a[j];
			}
		}
		printf("%d\n", max * 10);
	}
	return 0;
}

1个多小时的debug，终于用贪心做出来了。。。。各种悲剧啊  不过还是做出来了 爽歪歪啊

思路就是从头扫描，第一次把能一起完成的都完成，记录完成的推桌子数目。

第二次再从头扫描，把第二次能一起完成的都完成，记录第二次完成的推桌子数目。

循环，直到完成推桌子数目等于总桌子数目就可以退出了

其中比较难实现的就是怎么找从头开始扫描的底线，这个我是用visit数组+flag+for循环找到的，比较繁琐，但是还是实现了。。。看来只要肯动脑筋，还是能想出来的。。。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 210
bool visit[N * 2];

struct node
{
	int s, t;
}p[N];

bool cmp(const node &a, const node &b)
{
	return a.s < b.s;
}

int main()
{
	int ncase;
	int n;
	int cur, sum;
	int count;
	bool flag;
	scanf("%d", &ncase);
	while(ncase--)
	{
		sum = 10;
		count = 1;
		memset(visit, false, sizeof(visit));
		scanf("%d", &n);
		if(n == 0)
		{
			printf("0\n");
			continue;
		}
		for(int i = 0; i < n; ++i)
		{
			scanf("%d%d", &p[i].s, &p[i].t);
			p[i].s = (p[i].s + 1) / 2;
			p[i].t = (p[i].t + 1) / 2;
			if(p[i].s > p[i].t)
				swap(p[i].s, p[i].t);
		}
		sort(p, p + n, cmp);
		node cur;
		cur.s = p[0].s;
		cur.t = p[0].t;
		visit[0] = true;
		flag = false;
		for(int i = 0; i < n; i = (i + 1) % n)
		{
			if(n == count)
				break;
			if(flag == true) //新一轮扫描
			{
				for(int j = 1; j < n; ++j) //下次循环找第一个作为标准
				{
					if(!visit[j])
					{
						cur.s = p[j].s;
						cur.t = p[j].t;
						count++;
						sum += 10;
						visit[j] = true;
						flag = false;
						break; //找到就退出
					}
				}
			}
			if(i == n - 1) //一轮扫描结束，flag变true
				flag = true;
			if(!visit[i])
			{
				if(p[i].s > cur.t)
				{
					count++;
					visit[i] = true;
					cur.s = p[i].s;
					cur.t = p[i].t;
				}
			}
		}
		printf("%d\n", sum);    
	}
	return 0;
}

代码如下：