P1638 逛画展
1 #include <bits/stdc++.h> 2 #define LL long long 3 #define For(i,j,k) for(int i=j;i<=k;i++) 4 using namespace std ; 5 6 const int N = 1000011 ; 7 int n,m,ansl,ansr,le,ri ; 8 int a[N],f[2011] ; // 9 10 inline int read() 11 { 12 int x = 0 , f = 1 ; 13 char ch = getchar() ; 14 while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 15 while(ch>='0'&&ch<='9') { x = x * 10+ch-48 ; ch = getchar() ; } 16 return x * f ; 17 } 18 19 inline bool check(int len) 20 { 21 le = 1 ; ri = len ; 22 int cnt = 0 ; 23 For(i,1,m) f[i] = 0 ; 24 For(i,1,len) { 25 if(!f[a[i]]) cnt++ ; 26 f[a[i]]++ ; 27 } 28 if(cnt==m) return 1 ; 29 For(i,len+1,n) { 30 le = i-len+1 ; 31 ri = i ; 32 f[a[le-1]]-- ; 33 if(f[a[le-1]]==0) cnt-- ; 34 if(!f[a[ri]]) cnt++ ; 35 f[a[ri]]++ ; 36 if(cnt==m) return 1 ; 37 } 38 return 0 ; 39 } 40 41 int main() 42 { 43 n = read() ; m = read() ; 44 For(i,1,n) a[i]=read() ; 45 int l = 1 ,r = n+1 ; // 注意这边 r 要加1 防止 答案 r 取不到 46 while(l<r) { 47 int mid = (l+r)>>1 ; 48 if(check(mid)) { 49 r = mid ; 50 ansl = le ; 51 ansr = ri ; 52 } 53 else l=mid+1 ; 54 } 55 printf("%d %d ",ansl,ansr) ; 56 return 0 ; 57 }