[Leaf] [P1638] 逛画展

p1638-逛画展---洛谷">P1638 逛画展 - 洛谷

1. 题面梗概

在一个长度为 $n$ 的数列中，找出包含 $m$ 个不同数的最小连续区间。

若长度相同，则输出 $x$，最小的那一组。

2. 逻辑推导

我们需要寻找一个长度不定的区间，其实这是个滑动窗口问题。

对于一个 $[L,R]$ 的区间，我们的目的是找到最小的区间，

如果当前区间内已经满足条件，那么我们移动 $L \rightarrow L + 1$，收缩窗口。

如果当前区间不满足条件，那么我们移动 $R \rightarrow R + 1$，扩张窗口。

为什么可以这么想？—— 单调性。

随着右端点 $R$ 增加，区间内不同数的数量单调不减；若当前已集齐，右移 $L$ 仅会使区间更短。

通过上述描述，我们只需要再开一个计数数组 cnt[i]，记录 $i$ 这个数出现了多少次。

然后就是标准的双指针实现了。

2. 代码实现

▶

AcCode

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 50;
const int maxm = 2e3 + 50;

int cnt[maxm];
int a[maxn];
int n, m;

int main( ) 
{
    cin >> n >> m;
    for( int i = 1; i <= n; ++ i ) cin >> a[i];
    
    int ansl = 1, ansr = n;
    int anslen = n + 1;

    int l = 1, r;
    int cur_cnt = 0;

    for( r = 1; r <= n; ++ r )
    {
	    // 扩张
        if( cnt[ a[r] ] == 0 ) cur_cnt ++;
        cnt[ a[r] ] ++;
		
        while( cur_cnt == m )
        {
            int len = r - l + 1;
            if( len < anslen )
            {
                anslen = len;
                ansl = l, ansr = r;
            }
			
			// 收缩
            cnt[ a[l] ] --;
            if( cnt[ a[l] ] == 0 ) cur_cnt --;
            l ++;
        }
		
    }
	
    cout << ansl << " " << ansr << '\n';
    return 0;
}

4. 复盘

• 复杂度: $O(n)$。

• 碎碎念: 这种题基本思路就是通过双指针，把冗余的循环查人数降维。

• 关联知识点： 双指针