传送门：Cow Lineup
/********************** 题目来源：牛客假日团队赛45-B-Cow Lineup 题目链接：https://ac.nowcoder.com/acm/contest/6181/B 题目大意：有n头牛，每头牛都有一个编号，不同的牛可以共享一个编号， 问删掉k种编号的牛，最大可以有几头连续的牛编号相同 解题思路：尺取法（好久不写尺取复习一下），首先数据很大先离散化一下， 然后，l、r分别代表左右端点，维护一个区间，使得区间始终保持在牛的种类 小于等于k+1种，当等于k+2时，改变左端点的位置，每次更新ans，输出即可！ **********************/ #include<bits/stdc++.h> using namespace std; #define ll long long const int maxn = 1e5+5; int a[maxn],s[maxn];//a离散化好的数据，s表示区间内当前编号牛的数量 int main() { int n,k,ans=0,cnt=0; scanf("%d%d",&n,&k); map<ll,int>mp; for(int i=1;i<=n;i++){ ll x; scanf("%lld",&x); if(!mp[x]){ a[i]=++cnt; mp[x]=cnt; } else a[i]=mp[x];///离散化 } int l=1,r=0,p=0; while(r<n){ r++; if(!s[a[r]]) p++;//如果当前编号牛没有出现过，p++ s[a[r]]++; while(p==k+2){ s[a[l]]--;///移动左端点 if(!s[a[l]]) p--;///如果当前牛编号被删除完，p-- l++; } ans=max(ans,s[a[r]]);///更新答案 } printf("%d\n",ans); return 0; }
