HDOJ 1050 Moving Tables

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=1050

又是一道贪心题,不过和 HDOJ 1009HDOJ 2037不一样,这里是以局部最优反映了整体最优。

而其余2题是逐步求最优,不知道说清楚没,做了这三题就可以感觉出来了,这三题都是很经典的题目。

这题看见有人用类似上面2题的方法做了,我没去尝试,看见杭电的PPT里有更简单的方法,尝试了,写出来的代码简单易懂。

思路:首先要知道,最长的时间就是一个过道被经过的最大次数,这样题目就简单多了,求过道重复次数最大值,这里注意1,2和3,4等都是对门的,要采用减一后除以2的方法映射到同一坐标轴上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 #include <iostream>
#include <algorithm>
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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 1050 Moving Tables》有27个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注