1 #include<iostream> 2 using namespace std; 3 int n,m,a[1000005],b[2005]={0},i,j=0,step,k=0,h,e,s=0; 4 int main() 5 { 6 cin>>n>>m; 7 for(i=0;i<n;i++) cin>>a[i];//输入 8 for(i=0;k<m;i++) if(b[a[i]]++==0) k++;//第一种情况 9 for(step=e=--i;;)//遍历大约n种情况 10 { 11 for(b[a[j]]--;b[a[j]]==0;b[a[++i]]++) if(i==n) break; 12 if(i==n) break; 13 if(i-++j<step) {h=j;e=i;step=i-j;} 14 } 15 cout<<++h<<' '<<++e<<endl;//输出 16 }
1.先考虑第一种情况，即从第一个巧克力开始的情况
2.在上一种情况的基础上，放弃开头的巧克力ai，若第ai种巧克力数目降为0，需往后补巧克力直至重新出现数值为ai的巧克力
3.如此递推，若出现更短的巧克力序列，更新数据，直至“需要往后补时却没有巧克力”方可停止遍历