题型：综合题 题类：常考题 难易度：困难
浙江省高中信息技术 子序列问题练习
参选地区用数字1，2，3……N表示，每个地区所属的省份依次存入数组a(1)到a(N)，若1号地区的省份编号是3，即a(1)=3。分析可知，所求区间的长度至少为K(省份的数量)，最大为N(地区的数量)。我们可以通过二分K到N之间的数求得最小区间长度。例如有10个参选地区，分别来自于5个不同的省份，从左到右排列，地区编号依次为2，1，2，4，3，3，5，5，3，5，则最小的一段包含所有5个地区的区间是从第2个到第7个地区，区间长度为6。
Dim a(1 To 100) As Integer, K As Integer, N As Integer
Private Sub Form_Load()
‘产生N的值,表示地区数,产生K的值,表示省份数
‘产生编号为1到N的地区的省份编号,并存储在数组a中
‘代码略
End Sub
Private Sub Command1_Click()
Dim M As Integer
i = K: j = N
Do While i <= j
If bh(M) = True Then
j = M -1
ans = M
Else
i = M+1
End If
Loop
Text1.Text = Str(ans)
End Sub
Function bh(M As Integer) As Boolean
Dim f(1 To 25) As Integer ‘f(i)表示是否包含省份为i的地区
Dim t As Integer
bh= False
For i = 1 To N-M + 1 ‘枚举以i为起点的M个地区中各个省份是否都包含
For j =
f(a(j)) = 1
Next j
t= 0
For j = 1 To K
Next j
If t = K Then bh= True: Exit Function
For j = 1 To K
f(j) =0
Next j
Next i
End Function
试题篮
