SCNU省选校赛第二场B题题解

In the first sample among numbers a₁ and a₂ there are exactly two distinct numbers.

In the second sample segment [2, 5] is a minimal by inclusion segment with three distinct numbers, but it is not minimal in length among such segments.

In the third sample there is no segment with four distinct numbers.

题目理解的难点在于min区间的意思，所谓的min是不能在这个区间找到更小的满足。

这个区间的性质就是，恰好有k个不同的数字。

比如 n=5,k=3

1 1 2 3 4

满足区间性质的有: 1 1 2 3, 1 2 3,但是前者不是最小，因为其子区间1 2 3也满足。而1 2 3为最小的，因为没有其他子区间有三个不同数了。当然 2 3 4也是最小区间。

这样就有个问题了?怎么才叫最小呢？

比如 n=6, k=3,

1 1 2 1 2 3 

我们的策略就是从第一个开始找，找到区间含有k个数，马上就break掉，记下当前满足k个不同的大区间(不一定是min)

之后我们就确定了一个区间[1,end],之后从end开始找，找到区间含有k个数，马上就break掉，记下当前满足k个不同的子区间开始beg.

那么此时[beg,end]一定是最优的。

为什么呢？

我们可以这样考虑，因为区间要求是连续的，而end是第k个数，我们不能缺少这个数，所以第一次确定了end后，右边界就确定了，之后往左走，同理，在beg找到第k个（这时候我们看end是第一个数啦），我们就不能缺少beg的数，区间就不能比[beg,end]更小了，所以的出来的结果就是最优的。

我的代码：

/*******************************************************************************/
/* OS           : 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 UTC 2013 GNU/Linux* Compiler     : g++ (GCC)  4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)* Encoding     : UTF8* Date         : 2014-04-03* All Rights Reserved by yaolong.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
int mp[100005];
int main(){int n,k,i;int ind;vector<int> a;while(cin>>n>>k){memset(mp,0,sizeof(mp));a.clear();a.resize(n+1);for(i=1;i<=n;i++)cin>>a[i];int cnt=0;int beg=0;for(i=1;i<=n&&cnt<k;i++){if(mp[a[i]]==0){mp[a[i]]=1;cnt++;ind=i;}else{}}if(cnt!=k){cout<<-1<<" "<<-1<<endl;}else{memset(mp,0,sizeof(mp));for(i=ind;i>=1&&cnt>=0;i--){if(mp[a[i]]==0){mp[a[i]]=1;cnt--;beg=i;}}cout<<beg<<" "<<ind<<endl;}}return 0;}