【题解】逛画展

MikeC

发布于 2022-09-21 11:42:46

3750

文章被收录于专栏：MikeC's BlogMikeC's Blog

题目描述

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

wangjy想到博览馆去看这几位大师的作品。

可是，那里的博览馆有一个很奇怪的规定，就是在购买门票时必须说明两个数字，

a和b，代表他要看展览中的第 a 幅至第 b 幅画(包含 a 和 b)之间的所有图画，而门票

的价钱就是一张图画一元。

为了看到更多名师的画，wangjy希望入场后可以看到所有名师的图画(至少各一张)。

可是他又想节省金钱。。。

作为wangjy的朋友，他请你写一个程序决定他购买门票时的 a 值和 b 值。

输入格式

第一行是 N 和 M，分别代表博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。

其后的一行包含 N 个数字，它们都介于 1 和 M 之间，代表该位名师的编号。

输出格式

a和 b(a\le b) 由一个空格符所隔开。

保证有解，如果多解，输出a最小的。

输入输出样例

输入 #1

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

输出 #1

2 7

分析

分析题目，显然是要求在一个长度为 N，包含 M 种数的序列中找一个最短区间，使得所有数都出现一遍。我们可以考虑枚举区间，但这个区间可不是随便枚举的哈，我们是有备而来的，我们要用双指针优化。

利用两个指针 l 和 r 维护一个区间，一个哈希数组来维护每个数在区间中出现的次数，如果满足了所有的数都出现一遍，则尝试右移左指针缩小区间，否则右移右指针扩大区间来尝试满足条件。

时间复杂度 O(n)，常数偏大。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000001],k,hs[2001],l=1,r=1,ans_l=1,ans_r=1,ans=INT_MAX;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    hs[a[1]]++;k++;
    while(l<=r&&r<=n){
        if(k==m){
            if(ans>r-l+1){
                ans=r-l+1;
                ans_l=l;
                ans_r=r;
            }//更新答案 
            hs[a[l]]--;
            if(!hs[a[l]])k--;
            l++;//尝试将左端点向右，缩小区间 
        }else{
            r++;
            if(!hs[a[r]])k++;
            hs[a[r]]++;//被迫将右端点向右，扩大区间 
        }
    }
    printf("%d %d",ans_l,ans_r);
    return 0;
}

最后修改：2021 年 07 月 20 日 03 : 08 PM

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021 年 02 月，如有侵权请联系 cloudcommunity@tencent.com 删除

指针

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

指针

登录后参与评论

0 条评论

热度