poj 3190 Stall Reservations 贪心

缘起

日常浪费生命 poj 3190 Stall Reservations

分析

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
每头奶牛拥有自己的可以挤奶的时间。且，每头牛都必须挤奶，而他们又不愿意在一间房，问最少需要造多少间房。
并且输出任一种合法的安排方法

【输入】
第一行是奶牛的数量N(1 <= N <= 50000), 后面N行分别是每头奶牛挤奶的时间段[A,B]（1 <= A <= B <= 1e6）.

【输出】
最少几间房, 其次任一种合理的安排

【样例输入】
5
1 10
2 4
3 6
5 8
4 7

【样例输出】
4
1
2
3
2
4

【hint】
Time     1  2  3  4  5  6  7  8  9 10

Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>

Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..

Stall 3 .. .. c3>>>>>>>>> .. .. .. ..

Stall 4 .. .. .. c5>>>>>>>>> .. .. ..

【限制】
1s

【来源】
USACO 2006 February Silver

【是否接受特判】
是

贪心. 这个就是和之前最多完全参与多少件工作(活动安排问题)问题类似. 首先，将挤奶区间按照结束时间升序排序（这种贪心策略符合直观——我优先选择结束时间早的活动有利于选择更多后续活动）.

则每轮中，首先选择结束时间最小的, 然后选择开始时间严格大于前一个区间的结束时间的.

下面的代码细节上可能会遗忘，但是记住整体思路就是经典的贪心问题活动安排问题 ，每次使用活动安排问题的

贪心策略得到一批可以进同一槽的牛.

首先是被T掉的代码

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

struct Cow
{
	int a,b,i; // i是排序前的索引
	bool operator<(Cow o)
	{
		return b<o.b;
	}
}cow[50005];

int n,ss[50005],ans; // ss[i]=j 表示牛i要进入槽j哺乳, 为0表示尚未被安排

void sz()
{
	int m = n, i=1; // 尚未被安排的奶牛数量, i是当前需要安排的奶牛
	while(m)
	{
		ans++;
		ss[cow[i].i] = ans; // i被安排进入了ans这座槽, 后面将看看还有没有牛也能进此槽的
		m--; // 安排了一头牛
		int j = i+1,t=i;
		bool flag = false; // 有没有决定下一轮从哪头牛开始
		while(j<=n)
		{
			if (ss[cow[j].i]) // 如果已经被安排了, 就算了
			{
				j++;
				continue;
			}
			if (cow[j].a>cow[t].b)
			{
				ss[cow[j].i] = ans; // 和前一头牛哺乳区间不想交, 可以进同一座槽
				m--; // 安排了一头牛
				t = j;
			}
			else if(!flag)
			{
				i = j; // 下次就从这头牛开始
				flag = true;
			}
			j++;
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (int i = 1; i<=n;i++)
	{
		scanf("%d%d", &cow[i].a, &cow[i].b);
		cow[i].i = i;
	}
	sort(cow+1, cow+n+1);
	sz();
	printf("%d\n", ans);
	for (int i = 1; i<=n;i++)
	{
		printf("%d\n", ss[i]);
	}
	return 0;
}
Status Time Limit Exceeded
Length 1091
Lang C++
Submitted 2019-08-24 15:07:15
Shared
RemoteRunId 20795559

为什么会超时呢? 因为每次使用活动安排算法确定一批进入同一槽的牛的复杂度是O(n), 所以整体复杂度最坏可能到O(n^2) 而n达到了5w. 所以超时是必然的. 那么怎么优化呢?

其实很好优化——只需要开一个数组（5w长度的int数组）维护每个槽的最迟结束哺乳时间即可. 则每次考察排好序的数组的一头牛的时候，如果它的开始时间严格大于某个槽的最迟结束时间，则可以将其加入该槽并更新该槽的最迟哺乳结束时间. 如果它的哺乳开始时间<=任何一个槽的最迟结束时间的话, 则就要新开辟一个槽. 所以我们每次都要求 所有槽的最迟结束时间这一指标的最小值 一旦求出, 就知道了该最小值来自于哪个槽. 然后我们更新该槽的最迟结束时间. 所以需要使用堆优化. 复杂度降为 NlogN

ac代码

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
//#define LOCAL
typedef pair<int,int> P; // first表示

struct Cow
{
	int a,b,i; // i是排序前的索引
	bool operator<(Cow o)
	{
		return a<o.a; // 注意, 按照早开始进行排序, 而不是按照结束时间排序
	}
}cow[50005];

int n,ss[50005],ans; // ss[i]=j 表示牛i要进入槽j哺乳, 为0表示尚未被安排

void sz()
{
	priority_queue<P, vector<P>, greater<P> > pq; // 关于P.first的小根堆
	pq.push(P(cow[1].b,1)); // 首先1号槽里面只有一头牛——就是所有牛中结束哺乳最早的牛
	ans++; // 安排了第一头牛
	ss[cow[1].i] = 1; // 安排第一头牛进入1号槽
	int cur = 2; // 当前需要安排的牛
	while(cur<=n)
	{
		P top = pq.top();
		pq.pop();
		int a = top.first, i = top.second; //i号槽位最早结束哺乳, 最早结束的时间是a
		if (cow[cur].a<=a) // 如果比最早结束的还要早开始的话,只能另开一个槽了
		{
			pq.push(P(cow[cur].b, ++ans));
			ss[cow[cur].i] = ans; // cur 被安排进了一个新的槽
		}
		else // 则cur可以被安排进入i槽, 而不需要新安排槽
		{
			ss[cow[cur].i] = i;
			top.first = max(a,cow[cur].b); // 更新该槽的最迟结束哺乳时间,注意 cow[cur].b未必比top.first大, 所以这里要注意一下,wa了一发
		}
		pq.push(top);// 重新入堆
		cur++; // cur牛已经安排完毕,准备安排下一头牛
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (int i = 1; i<=n;i++)
	{
		scanf("%d%d", &cow[i].a, &cow[i].b);
		cow[i].i = i;
	}
	sort(cow+1, cow+n+1);
	sz();
	printf("%d\n", ans);
	for (int i = 1; i<=n;i++)
	{
		printf("%d\n", ss[i]);
	}
	return 0;
}

ac情况

Status Accepted
Time 219ms
Memory 1276kB
Length 1321
Lang C++
Submitted 2019-08-24 16:09:50
Shared
RemoteRunId 20795927