poj 1065 Wooden Sticks 贪心

缘起

日常水题 poj 1065 Wooden Sticks

分析

题意很简单

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
给你N根木头，每根的长度和质量l和w. 要加工这些木头，但是机器开启预热时间是1分钟. 如果后面加工的木头的长度和
质量都>=前一根的话，则加工完前一根木头来加工后一根木头的话是不需要预热的, 否则也需要预热一分钟
求加工顺序使得预热总时间最短.

【输入】
多样例, 第一行是样例数. 每个样例第一行是N(1<=n<=5000), 第二行包含2n个<=10000的正整数
l1,w1,l2,w2,....,ln,wn

【输出】
每个样例输出最小预热时间.

【样例输入】
3 
5 
4 9 5 2 2 1 3 5 1 4 
3 
2 2 1 1 2 2 
3 
1 3 2 2 3 1

【样例输出】
2
1
3

【限制】
1s

从贪心的角度，显然答案应该是木头中非降子序列的个数（这些子序列应该一个接一个的排着，而不能犬牙交错）. 例如

1
( 9 , 4 ) , ( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , ( 4 , 1 )

则有

1
2
3
( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 ) 
和
( 1 , 2 ) , ( 2 , 5 )

2个非降子序列. 则答案就是2, 因为排列成

1
( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 ) , ( 1 , 2 ) , ( 2 , 5 )

即可（即一个非降子序列接着后一个非降子序列即可）

所以问题转换为求给定序列中重排序之后最少能凑成的非降子序列的个数.

但是注意题目是二维的. 所以首先按照一维进行排序（第二维也升序），然后要的答案就在这个序列中（你反正第一维肯定是要升序的）

怎么求呢? 也是贪心——伊始所有的木棍都是没有标记的. 然后只要不是所有的木棍都标记了，找到第一个没有被标记上的木棍，然后向后遍历，找出单增的子序列即可, 找到最后，则单增群落数量+1, 最终，单增群落的个数就是答案.

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
//#include "stdafx.h"

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

int n,ans;

bool tag[5005];

struct Wood
{
	int l,w;
	bool operator <(Wood o)
	{
		return l==o.l?w<o.w:l<o.l; // 按照l升序排序, 如果l相等, 按照w升序排序
	}
}cccc[5005];

void sieve() // 和素数筛法很相似
{
	for (int i = 0; i<n;i++)
	{
		if (!tag[i])
		{
			tag[i] = true;
			ans++;
			Wood t = cccc[i];
			int j = i+1;
			while(j<n)
			{
				if (t.w<=cccc[j].w && !tag[j]) // t.l肯定是非降的（已经排过序了）, 所以不需要比较t.l
				{
					tag[j] = true;
					t = cccc[j];
				}
				j++;
			}
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		ans = 0;
		memset(tag, 0, sizeof(tag));
		scanf("%d", &n);
		for (int i = 0; i<(n<<1); i+=2)
		{
			scanf("%d%d", &cccc[i>>1].l, &cccc[i>>1].w);
		}
		sort(cccc, cccc+n);
		sieve();
		printf("%d\n", ans);
	}
	return 0;
}

ac情况

Status Accepted
Time 16ms
Memory 128kB
Length 949
Lang C++
Submitted 2019-08-28 09:44:39
Shared
RemoteRunId 20810357

参考

【1】https://yfsyfs.github.io/2019/08/19/poj-2533-Longest-Ordered-Subsequence-LIS-dp-%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97/