n733. 11536 - Smallest Sub-Array
標籤 :
通過比率 : 5人/6人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-07-16 13:48

內容

考慮一個包含 N 個元素的整數序列,其中:

找到兩個數值 a 和 b,使得序列 (Xa Xa+1 Xa+2 ... Xb−1 Xb) 包含從 1 到 K 的所有整數。如果有多個解,則確保 (b − a) 最小。

換句話說,找到給定序列中包含從 1 到 K 的所有整數的最小子序列。

考慮一個例子,N = 20,M = 12 和 K = 4。 序列為 {1 2 3 7 1 12 9 11 9 6 3 7 5 4 5 3 1 10 3 3}。 包含所有整數 {1 2 3 4} 的最小子序列長度為 13,並且在以下序列中高亮顯示: {1 2 3 7 1 12 9 11 9 6 3 7 5 4 5 3 1 10 3 3}。

輸入說明

輸入的第一行是一個整數 T(T < 100),表示測試案例的數量。每個測試案例由一行包含三個整數 N(2 < N < 1000001)、M(0 < M < 1001)和 K(1 < K < 101)組成。這些變量的含義如上所述。

輸出說明

對於每個測試案例,輸出案例編號以及最小的子序列長度。如果沒有有效的子序列,輸出「sequence nai」。具體格式請參考範例。

範例輸入 #1
2
20 12 4
20 12 8
範例輸出 #1
Case 1: 13
Case 2: sequence nai
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1K
提示 :
標籤:
出處:
UVA [管理者: ig99lp33lp33 (위즈원) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」