USTC 1151（Shortest Subsequence）

题目大意：题意很简单,就是在一串数字中找到一个子串,使得这个子串包含 1~n 的每一个数至少一次且长度最短。解法复
杂度是 O(n)的,做一次从左往右的扫描即可
题目分析：这道题刚开始不知道怎么做，后来请教别人 然后看完解题报告终于明白这个精妙的维护过程！

首先在sim[]数组里存放各个输入的数据，flag[i],表示i在子串里出现的次数！然后用两个指标i,j分别从第一位扫描！

在这里j是代表一个子串的开头，i代表一个子串的结尾，用i遍历完一次就可以求出最短子串，

for i : 1->t

   1） 如果sim[i]是1~n里的数，进一步判断他是不是第一次出现在这个子串里，如果是total++（total是记录有多少个1～n里的数出现过的变量）

         然后把 flag [ sim[ i ] ] + 1(不管是不是第一次出现，这里都要+1！),   

  2)     在j不超过i的前提下，对j的位置进行优化，首先如果j位上的数在子串里出现了2次或者2次以上说明我们最短子串里不需要包括

          j位上的数，把j向右移动一位。

  3） 判断子串里是不是包括里所有1~m里的数，并且判断这个子串的长度是不是比上一个满足条件的子串短，如果两个条件都满足，我们分别更新记录最短子串的开头和结尾的两个变量：sn,en；

源程序+部分注释：

#include<iostream>
#include<cstdio>
using namespace std;

int sim[1000020],n,t;

bool init(){
	scanf("%d %d",&n,&t);
	if(n==0&&t==0)
		return false;
	for(int i=1;i<=t;i++)
		scanf("%d",∼[i]);
	return true;
}

void solve(){
	int i,j,sn,en,total;
	sn=1;	en=t;
	int flag[5020]={};
	total=0;
	for(i=1,j=1;i<=t;i++){
		if(sim[i]>=1&∼[i]<=n){
			if(flag[sim[i]]++==0)
				total++;
		}
		while(j<=i){
			if(flag[sim[j]]==1)
				break;
			flag[sim[j]]--;
			j++;
		}
		if(total==n&&i-j<en-sn){
			sn=j;
			en=i;
		}
	}
	if(en==t)
		printf("-1\n");
	else
		printf("%d %d\n",en-sn+1,en);
}

int main(){
	while(init()){
		solve();
	}
	return 0;
}