P1638 逛画展

题目描述

博览馆正在展出由世上最佳的 m 位画家所画的图画。

游客在购买门票时必须说明两个数字，a 和 b，代表他要看展览中的第 a 幅至第 b 幅画（包含 a,b）之间的所有图画，而门票的价钱就是一张图画一元。

Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购买门票的价格。

请求出他购买门票时应选择的 a,b，数据保证一定有解。

若存在多组解，输出 a 最小的那组。

输入格式

第一行两个整数 n,m，分别表示博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。

第二行包含 n 个整数 $a_i$，代表画第 i 幅画的名师的编号。

输出格式

一行两个整数 a,b。

输入输出样例

输入 #1

12 5
2 5 3 1 3 2 4 1 1 5 4 3

输出 #1

2 7

说明/提示

数据规模与约定

• 对于 30% 的数据，有 $n\le200,m\le20$。
• 对于 60% 的数据，有 $n\le10^5,m\le10^3$。
• 对于 100% 的数据，有 $1\leq n\le10^6,1 \leq a_i \leq m\le2\times10^3$。

题目解析

仔细阅读题目发现，实际题目要求的是：寻找满足区间内具有m个不同元素的最小区间。

暴力方式就是枚举区间开始与区间结束，逐一遍历区间内元素，统计是否具有m个不同元素。根据数据规模，大概是能拿30分。

此时需要进一步优化。仔细观察要求的区间是连续的；另，可发现题目要求的答案是由两个条件组成：

1. 区间内不重复的元素个数有m个。
2. 满足条件1的前提下，区间要最小。

那么我们可以利用双指针处理，先移动右指针，满足条件1；再移动左指针，在满足条件一的基础上不断缩减区间，直到不满足条件1位置。之后重复之前的步骤，直到遍历完所有元素。

此时，由于两个指针同向而行，每个元素只需遍历一次，时间复杂度为$O(n)$。

代码实现

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e6+5;
int a[N];
int n,m;
int v[2005];//v[x]=画家x在区间内出现的次数
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int l=1,r=1;//左右指针
    int cnt=1;//区间内不同元素个数 ，预处理第一个元素
    v[a[l]]=1;//处理第一个元素
    int L=1,R=n;//答案区间的左右端点
    while(l<n && r<n){//在范围内移动
        while(r<n && cnt<m){//右指针移动，直到区间内包含所有的画家(不同元素个数为m)
            r++;//移动右指针
            v[a[r]]++;//统计出现次数
            if(v[a[r]]==1){//判断是否第一次出现
                cnt++;//不同元素数量增加
            }
        }
        while(l<=r && cnt==m){//移动左指针
            if(r-l<R-L){//若当前满足条件1的区间小于记录的答案区间
                //更新区间端点
                R=r;
                L=l;
            }
            v[a[l]]--;//统计数量，左指针对应的要从区间内去掉
            if(v[a[l]]==0) cnt--;//更新
            l++;//移动左指针
        }
    }
    cout<<L<<" "<<R;//输出答案
    return 0;
}