小朋友拍照

题目描述:

有来自K（1<=K<=100）个不同国家的N(1<=N<=1000)个小朋友排成一行准备拍照。国籍用数字1,2,3……N表示，每个小朋友的国籍依次存入数组a[1]到a[K]。
由于小朋友太多，没有办法全部被拍入。摄像师决定拍摄一段连续区间内的小朋友，这个区间内每种国籍的小朋友至少要有1个，求满足要求的最小区间长度。
例如有10个小朋友，5种国籍，从左到右排列，国籍编号依次是2，1,2,4,3,3,5,5,3,5，则最小的一段包含所有5种国籍的区间是从第2个到第7个小朋友，区间长度为6。

输入格式:

第一行两个整数，n和k，表示有n个小朋友，k个不同的国家。

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

输出格式:

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

数据范围:

n<=1000

k<=100

样例输入:

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

样例输出:

6

提示:

样例解释：

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

#使用二分的思想计算最小区间
f = [ 0 ] * 101                    #f[i]表示国籍为i的小朋友是否包含
n, k = map( int ,input().split() )
a = [0] + list( map( int ,input().split() ) )

def pd( m ):    
    pd = False
    for i in range( ______(1)_______ ): #枚举以i为起点的M个小朋友中，各个国籍是否包含
        for j in range(1, k +1 ):      #f数组元素重新初始化为0
            f[ j ]  = 0
        for j in range( i, i+m ):
            f [ a[j] ] = 1          #等于1，表示国籍为a(j)的小朋友已包含，0表示不包含
        t = 0                       #t用于统计当前区间包含的国籍数量
        for j in range( 1, k+1 ):      #统计已包含的国籍的数量
            t = ________(2)_________
        if t == k :
            pd = True
            break   #若包含K个国籍，返回True
        
    return pd

i = k; j = n              #答案的范围为K到N，即最少K，最多N个小朋友
while i <= j:    
    m = (i + j) // 2      #二分，求中间值
    if pd( m ) == True :  #调用Pd函数，判断区间长度为M时，是否包含所有国籍
        ans = m           #若以M为区间长度可包含所有国籍，更新答案
        j = m - 1        
    else :
        i = ________(3)_________
print( ans )

 

完善程序二：

n, k = map( int, input().split() )
a = [0] + list( map( int, input().split() ) )
b = [ 0 for i in range( k + 1 ) ]
L = 1; R=1; sum=0;  minn=1e9

while R <= n :   #双指针算法   R与L这两个变量的作用，好好理解
    
    while sum == k :
        
        L += 1
    R += 1

print( minn )

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

---

来源: 原创