#4992. 2026/2/25/LH笔记(尺取法)

2026/2/25/LH笔记(尺取法)

当前没有测试数据。

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10;
int t,n,a[N][N],b[N][N];
int m,n,a[N],b[2010],ans=1e9,type;
// string s[N][N];
// s[i][j]从起点出发 到(i,j)这个点,采摘的花生最多的时候  
// 具体路径是什么
// b[i][j]存的是从起点到(i,j)这个点 最多能摘多少花生
// b[i][j]=max(b[i][j-1],b[i-1][j])+a[i][j];
//尺取法---> 毛毛虫
//尺取法的核心思想
//用双指针选取一段范围,
//如果这段范围符合条件 1.比较答案 2.移动指针
//如果当前这段范围不符合条件 只移动另外一个指针
//尺取法题型1:区间和>=m 但是区间长度最短
//尺取法题型1:区间和<=m 但是区间长度最长
//尺取法题型2:利用下标计数+尺取法 解决 凑齐所有种类 最小长度/最小代价问题
//尺取法题型3:题目条件隐藏深一些,不容易发现是尺取法
//黑白奶牛:题目说最多只能使用k次魔法---->你可以选一段连续的范围,但是这一段范围内黑色的奶牛数量<=k
int main(){
   cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    int l=1,r=1;
    type=1;
    b[a[1]]=1;
    while(l<=n&&r<=n){
        if(type==m){
            ans=min(ans,r-l+1);
            b[a[l]]--;
            if(b[a[l]]==0) type--;
            l++;
        }else{
            r++;
            b[a[r]]++;
            if(b[a[r]]==1) type++;
        }
    }
    if(ans==1e9) ans=-1;
    cout<<ans;

    return 0;
}