poj 3320 Jessica's Reading Problem 尺取法

缘起

日常浪费生命 poj 3320 Jessica’s Reading Problem

分析

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
为了备考，杰西卡开始阅读一本很厚的书籍. 要想通过考试，显然需要把课本中所有的知识点都掌握.
此书P页. 第i页恰好一个知识点ai(假定每个知识点都有一个整数编号)
全书中同一个知识点会被多次提及. 所以希望通过阅读其中一些连续的页把所有知识点覆盖到. 给定每页的知识点
求出要阅读的最少页数.

【输入】
第一行是P(1 ≤ P ≤ 1000000), 第二行是P个非负整数表示每一页展示的知识点.

【输出】
最少要读几页

【样例输入】
5
1 8 8 8 1

【样例输出】
2

【限制】
1s

【hint】
读第一页和第二页即可

【来源】
poj月赛

尺取法. 首先要统计有哪些知识点. 然后开一个bool数组哈希之. 然后放一条尺取虫在上面开始爬. 其实和【1】的思路是一样的（【1】中已经讲解了尺取法的套路, 不明白的童鞋可以参考【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
68
69
70
71
72
73
74
75
76
77
78
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxn = 1000005;
int p, kk[maxn], t[maxn],num,v[maxn]; // num 是尚未被覆盖的知识点的个数,v[i]表示知识点i被覆盖的次数

void discrete(int x[],int y[], int n) // 离散化x[0,...,n-1], x的长度是n, y用于暂存x
{
	memcpy(y,x,n*sizeof(int));
	sort(y,y+n);
	num = unique(y,y+n)-y; // 去重之后剩下的元素个数, 即去重排序之后的元素在y[0,...,res-1]中,严格单增
	for (int i = 0; i<n;i++)
	{
		x[i] = lower_bound(y,y+num, x[i])-y;
	}
} // 离散化模板

int chiqu() // 尺取法
{
	int ans = ~0u>>1,lo = 0, hi = 0; // 当前尺取虫覆盖的范围是[lo,hi]
	num--; // 第一页书已经覆盖掉一个知识点了
	v[kk[0]] = 1; // kk[0]这个知识点已经被覆盖了一次
	while (1)
	{
		// 首先是尺取虫的头部进动
		while(hi<p&&num) // 只要知识点没有全部覆盖掉, 而且尺取虫的头部还可以继续向前
		{
			hi++;
			if (!v[kk[hi]])
			{
				num--; // 又覆盖了一个新的知识点
			}
			v[kk[hi]]++;
		}
		if (hi==p) // 如果尺取虫到头也没有覆盖全部知识点的话, 则尺取法结束
		{
			return ans;
		}
		// 说明hi<p && num减为0了，即覆盖掉了全部知识点
		ans = min(ans, hi-lo+1); // 更新一波ans
		// 尺取虫的尾部开始进动了
		while(lo<=hi&&!num)
		{
			v[kk[lo]]--; // kk[lo]这个知识点被覆盖的次数-1
			if (!v[kk[lo]]) // 如果此知识点kk[lo]没有被覆盖了
			{
				num++;
			}
			lo++;
		}
		if (lo>hi) // 说明一页就能覆盖所有知识点了
		{
			return 1;
		}
		// 此时 lo<=hi 并且 num=1, 说明lo-1~hi 就能覆盖掉所有知识点, 所以再更新一波答案
		ans = min(ans, hi-lo+2);
	}
	return ans; // 其实一定会在上面进行return的, 代码其实不会走到这里的
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &p);
	for (int i = 0; i<p; i++)
	{
		scanf("%d", kk+i);
	}
	discrete(kk,t, p);
	printf("%d\n", chiqu());
	return 0;
}

ac情况

Status Accepted
Time 235ms
Memory 944kB
Length 1512
Lang C++
Submitted 2019-09-01 17:47:24
Shared
RemoteRunId 20823743

尺取法思想简单，但是代码实现起来比较精细.

参考

【1】https://yfsyfs.github.io/2019/08/23/poj-3061-Subsequence-%E5%B0%BA%E5%8F%96%E6%B3%95/