Lotplace

本人於該blog的全部文章轉移至[UVA] 11536 Smallest Sub-Array – KKWBlog (kkwtech.com)該網域下，其後此處不進行更新，一律於新站點更新。

題目: 11536.pdf (nsysu.edu.tw)

題目說明:

給定N,M,K並依照題目構建一個數列，找出最短且包含1~K數字的sub array，並輸出該長度。

解題思路:

運用queue將符合條件的sub array的數字放入queue，若queue.front的數字重複出現於queue裡則將其pop出來，可以於走訪數列時維持相對短的sub array，並且在1~Ｋ都在queue裡時得到長度，最後將長度取最小即為該題解答

步驟：

1.創建1陣列存放<=k的數字最後出現的index last_pos
2.創建queue
3.宣告長度minlen及計算sub array裡不重複的數字個數count
4.依題目建構一個數列x
5.針對每個cur = x[i] ，將其i放入queue中
6.若是cur符合sub array的條件範圍則將last_pos[cur] = i，又若last_pos[cur]在此之前尚未放入queue中即為初始值的話，count++
7.將queue.front != last_pos[x[queue.front]]的元素pop出來
8.若是count == K則取一次最小長度
9.輸出長度
補充:
以last_pos紀錄數字最後出現的index可以確定位於queue裡的數字是否重複，因為queue裡的就是數字的index in x，所以若是該數字last_pos不等於queue.front的話，代表後面又走訪過該數字，即重複

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
    int Case = 1;
    int n;
    cin >> n;
    while(n--) {
        int n,m,k;
        cin >> n >> m >> k;

        //初始化陣列
        vector<int> x(n + 1,0);
        x[1] = 1;
        x[2] = 2;
        x[3] = 3;
        for(int i = 4; i <= n; i++) {
            x[i] = (x[i - 1] + x[i - 2] + x[i - 3]) % m + 1;
        }

        vector<int> last_pos(k + 1,0);
        int count = 0;//紀錄已出現的1~k總數，等於k即全部出現
        queue<int> subarr;//放入小於k的數字之index
        int minlen = 1000001;
        for(int i = 1; i <= n; i++) {
            int cur = x[i];
            if(cur >= 1 && cur <= k) {
                subarr.push(i);
                if(last_pos[cur] == 0) {//CHECK該數字是否為第一次出現
                    count++;
                }
                last_pos[cur] = i;//RECORD LAST POSITION
                while(subarr.front() != last_pos[x[subarr.front()]]) {//POP THE DUPLICATED NUMBER
                    subarr.pop();
                }
                if(count == k) {
                    minlen = min(minlen,subarr.back() - subarr.front() + 1);
                }
            }
        }

        if(minlen == 1000001) {
            printf("Case %d: sequence nai\n",Case++);
        }
        else {
            printf("Case %d: %d\n",Case++,minlen);
        }
        
    }
}

時間複雜度: O(N)

ghost

Filed under: UVA - @ 2021 年 9 月 17 日 上午 11:15

標籤: uva