首页 > 其他分享 >P1638 逛画展

P1638 逛画展

时间:2024-01-16 18:34:16浏览次数:43  
标签:画展 int 题解 cin tie P1638 指针

原题链接

反思,debug不出来就赶紧看题解把!

题解

双指针,双指针有好几种,这个是像弹簧(窗口)一样的双指针,右指针一直往右走,当成立时,左指针一直往左走直到不成立

code

#include<bits/stdc++.h>
using namespace std;
int a[1000006]={0};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    map<int,int> cnt;
    int l=1,minlen=n+1,ends,uni=0,start;
    for(int i=1;i<=n;i++)
    {
        if(cnt[a[i]]++==0)uni++;
        while(uni==m)
        {
            if(i-l+1<minlen)
            {
                minlen=i-l+1;
                start=l;
                ends=i;
            }
            if(--cnt[a[l++]]==0)uni--;
        }
    }
    cout<<start<<" "<<ends;
    return 0;
}

标签:画展,int,题解,cin,tie,P1638,指针
From: https://www.cnblogs.com/pure4knowledge/p/17968271

相关文章

  • AI壁纸画展头像表情包流量主微信抖音小程序开源版开发
    AI壁纸画展头像表情包流量主微信抖音小程序开源版开发以下是AI壁纸画展头像表情包流量主微信抖音小程序开源版的开发功能列表:用户注册和登录:实现用户注册和登录功能,包括手机号登录、第三方登录等方式。图片上传和展示:用户可以上传自己的图片或选择系统提供的图片进行展示,支持图片......
  • 逛画展(双指针)
    #逛画展##题目描述博览馆正在展出由世上最佳的$m$位画家所画的图画。游客在购买门票时必须说明两个数字,$a$和$b$,代表他要看展览中的第$a$幅至第$b$幅画(包含$a,b$)之间的所有图画,而门票的价钱就是一张图画一元。Sept希望入场后可以看到所有名师的图画。当然,他想最小......
  • P1638 逛画展
    浅浅证明一下这种做法的正确性。首先,答案一定是一个最优解,那么枚举右端点到b的时候,由于最优解是合法解,我们的左端点会走到不能走了为止,这样就求出了最优解,而且最优解一定是最小的,所以一定会记入答案。其实可以理解为把区间按照右端点分类了,而且每类区间中的最优解的左端点是递增......
  • P1638 逛画展
    逛画展题目描述博览馆正在展出由世上最佳的m位画家所画的图画。游客在购买门票时必须说明两个数字,a和b,代表他要看展览中的第a幅至第b幅画(包含a,b)之间的所有......
  • LOJ #3011. 「JOI 2019 Final」画展
    题目链接:​​传送门​​用最大的画框配最大的画显然是最优的那么挨个匹配就行#include<bits/stdc++.h>#defineusingnamespacestd;typedeflonglongll;pair<int,int>......
  • 六岁女儿的“小画展”
    家里大闺女喜欢画画做手工,有时候画了画,做了手工,都没保留下来,现在觉得挺可惜的。都是成才的记录,应该保存一下的好。下面是她之前画的画儿,记录一下:都是三岁到六岁半这段时间......