洛谷1638（尺取）
题目描述
博览馆正在展出由世上最佳的 M 位画家所画的图画。
wangjy想到博览馆去看这几位大师的作品。
可是，那里的博览馆有一个很奇怪的规定，就是在购买门票时必须说明两个数字，a和b，代表他要看展览中的第 a 幅至第 b 幅画(包含 a 和 b)之间的所有图画，而门票的价钱就是一张图画一元。
为了看到更多名师的画，wangjy希望入场后可以看到所有名师的图画(至少各一张)。可是他又想节省金钱……
作为wangjy的朋友，他请你写一个程序决定他购买门票时的 a 值和 b 值。
输入输出格式
输入格式：
第一行是 N 和 M，分别代表博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。
其后的一行包含 N 个数字，它们都介于 1 和 M 之间，代表该位名师的编号。
输出格式：
a和 b(a<=b) 由一个空格符所隔开。
保证有解，如果多解，输出a最小的。
样例：
输入：
12 5
2 5 3 1 3 2 4 1 1 5 4 3
输出：
2 7
思路：尺取法，cf常用标签two pointers，一种简单题目里常见的手段，难题没做过不知道:-)。虽然算法本身较简单（以致很多人在学到这个算法之前其实就已经在用了），就是两个指针一前一后去取区间看看行不行，但不熟练还是会翻车的，比如本垃圾，嘤嘤嘤。
这题思路直观不细讲了，然后浅谈一下这个方法的起手式吧：
1.l = 1， r = 0；
2.while循环里先用r往右试探，探到了或者到头了就停；
3.然后用l往右探，不满足条件了就停；
4.更新答案，然后如果发现指针没什么前途了就break出去输出答案。
以下是我的代码（主要部分），我对尺取法并没太多的接触，所以随便写一写的，欢迎大家交流自己的想法：
const int maxn = 1e6 + 5;
int n, a[maxn], m, p, l, r;
int in[2005], ansl, ansr, ans = inf;
int main() {
read(n), read(m);
rep(i, 1, n) read(a[i]);
l = 1, r = 0, p = 0;//in数组记录区间内有多少个某大师；p记录区间内共多少种大师//过程参照上述起手式
while (true) {
bool flag1 = false, flag2 = false;
while (p < m && r < n) {
flag1 = true;
if (!in[a[++r]]) p++;
in[a[r]]++;
}
while (p == m && l < r) {
flag2 = true;
if (in[a[l]] == 1) p--;
in[a[l++]]--;
}
if (p + flag2 == m && r - l + 1 + flag2 < ans) {//flag2的操作是我发现会漏情况临时补的qwq
ans = r - l + 1 + flag2;
ansl = l - flag2, ansr = r;
}
if (not flag1 && not flag2) break;
}
printf("%d %d\n", ansl, ansr);
return 0;
}最后，下次想要更难的题还是更简单的题吖？欢迎预定～^_^
温馨提示
如果你喜欢本文，请分享到朋友圈，想要获得更多信息，请关注ACM算法日常。