n<=100000個數，求刪掉K種相同的數之后最長的相同數區間長度。

原來是2指針裸題。兩個指針，一個左邊開始掃，一個右邊找最長的區間，使得數字種數不超過K+1即可，然后統計答案。

統計答案時，如果枚舉左端點就用左端點更新答案，枚舉右端點就用右。因為這個WA了兩次。

1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 //#include<math.h> 5 #include<algorithm> 6 #include<iostream> 7 using namespace std; 8 9 int n,m; 10 #define maxn 100011 11 int a[maxn],li[maxn],cnt[maxn]; 12 int main() 13 { 14 scanf("%d%d",&n,&m); 15 for (int i=1;i<=n;i++) scanf("%d",&a[i]),li[i]=a[i]; 16 sort(li+1,li+1+n);for (int i=1;i<=n;i++) a[i]=lower_bound(li+1,li+1+n,a[i])-li; 17 int l=1,r=1,tot=0,ans=0; 18 memset(cnt,0,sizeof(cnt)); 19 for (;l<=n;l++) 20 { 21 for (;r<=n;r++) 22 { 23 if (!cnt[a[r]]) tot++; 24 if (tot>m+1) {tot--;break;} 25 cnt[a[r]]++; 26 } 27 ans=max(ans,cnt[a[l]]); 28 cnt[a[l]]--; 29 if (!cnt[a[l]]) tot--; 30 } 31 printf("%d\n",ans); 32 return 0; 33 } View Code

?

轉載于:https://www.cnblogs.com/Blue233333/p/7608563.html

總結

以上是生活随笔為你收集整理的BZOJ3048: [Usaco2013 Jan]Cow Lineup的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。