奔跑吧，兄弟

题目描述:

“奔跑吧，兄弟” 栏目组要在全国各地挑选节目录制的地点。有来自 K（1<=K<=100）个不同地区的 N(K<=N<=20，000)个选手送来了各自的竞选材料。由于参加的选手太多，没有办法同时呈现所有材料供评委进行选择。栏目组决定选择一段连续区间内的个人参选材料，这个区间内每个地区的参选选手至少要有 1名，求满足要求的最小区间长度。

输入格式:

 第一行两个整数，n和k，表示有n个选手报名，k个不同的地区。

接下来n个数不大于k的整数，每两个数之间用一个空格隔开。

输出格式:

一个整数，表示最小长度的满足区间。

样例输入:

10 5
2 1 2 4 3 3 5 5 3 5

样例输出:

6

提示:

样例解释：

要覆盖5个地区的至少一名选手，那么最短长度的区间是从2个开始连续取6名选手， 1 2 4 3 3 5。

 

请完善下列程序（需要优化才能得满分）：

//使用二分的思想计算最小区间
#include <bits/stdc++.h>
using namespace std;
int f[101], a[20101], k, n, ans;
//f[i]表示国籍为i的小朋友是否包含

bool pd( int m ) {
	for (int i =1; i<= _______(1)_______; i++) { //枚举以i为起点的M个小朋友中，各个国籍是否包含
		for (int j =1; j<=k; j++ )     //f数组元素重新初始化为0
			f[ j ] = 0;
		for ( int j=i; j<=i +m -1; j++ )
			f [ a[j] ] = 1 ;         //等于1，表示国籍为a(j)的小朋友已包含，0表示不包含
		int t = 0 ;                   //t用于统计当前区间包含的国籍数量
		for ( int j=1; j<=k; j++)  //统计已包含的国籍的数量
			_______(2)________		  //填空2
		if ( t == k) 
			return true;          //若包含K个国籍，返回True
	}
	return false;
}

int main() {
	cin >> n >> k;
	for ( int i=1; i<=n; i++ ) cin >> a[i];
	int i = k;
	int j = n ;             //答案的范围为K到N，即最少K，最多N个小朋友
	while (i <= j) {
		int m = (i + j) / 2  ;    		//二分，求中间值
		if ( pd( m ) == true ) {	//调用Pd函数，判断区间长度为M时，是否包含所有国籍
			ans = m ;          		//若以M为区间长度可包含所有国籍，更新答案
			j = m - 1 ;
		} else
			i = _____(3)_______;   			//填空3
	}
	cout << ans ;
	return 0;
}

时间限制: 1000ms
空间限制: 256MB

---

来源: 原创