画展p1638

首先介绍尺取（双指针） 用于求解满足条件的最小区间问题 首先，从数组最左边元素开始，向右延伸r，使得最初满足条件。此时对于l为1来说，是最小的满足条件区间 接下来，开始将l变为2。变为2后，需要将r延长到能够满足条件的下一个r（可能不用延长，也可以先延长再把l变成2）。这样就得到了l为2时的最小区间 ......

# 逛画展 ## 题目描述 博览馆正在展出由世上最佳的 $m$ 位画家所画的图画。 游客在购买门票时必须说明两个数字，$a$ 和 $b$，代表他要看展览中的第 $a$ 幅至第 $b$ 幅画（包含 $a,b$）之间的所有图画，而门票的价钱就是一张图画一元。 Sept 希望入场后可以看到所有名师的图画。 ......

浅浅证明一下这种做法的正确性。 首先，答案一定是一个最优解，那么枚举右端点到b的时候，由于最优解是合法解，我们的左端点会走到不能走了为止，这样就求出了最优解，而且最优解一定是最小的，所以一定会记入答案。 其实可以理解为把区间按照右端点分类了，而且每类区间中的最优解的左端点是递增的（和右端点正相关）， ......

题目描述 博览馆正在展出由世上最佳的 $m$ 位画家所画的图画。 游客在购买门票时必须说明两个数字，$a$ 和 $b$，代表他要看展览中的第 $a$ 幅至第 $b$ 幅画（包含 $a,b$）之间的所有图画，而门票的价钱就是一张图画一元。 Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购 ......