UVa 11536 – Smallest Sub-Array [双指针]

点击打开UVa题目链接

题意

给定一个N个1-M的整数组成的序列。输入k,你的任务是找一个尽量短的连续子序列,使得该序列中包含1~K的所有整数。

分析

当年做的LeetCode的双指针题目今天终于派上用场了,刚开始枚举+二分超时了,后来想到了双指针。用map存当前两个指针内含有的数,并且更新最优值。

CPP代码

#include <bits/stdc++.h>
using namespace std;

const int maxm = 1024;
int N, M, K, ans, val[1000010];
map<int, int> cnt;

int main() {
    int T, kase = 0; scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d", &N, &M, &K);
        val[1] = 1, val[2] = 2, val[3] = 3;
        for(int i = 4; i <= N; ++i)
            val[i] = (val[i-1] + val[i-2] + val[i-3]) % M + 1;
        cnt.clear(); ans = INT_MAX;
        for(int st = 1, ed = 1; ed <= N; ++ed) {
            if(val[ed] > K) continue;
            else ++cnt[val[ed]];
            while(st < ed && (val[st] > K || cnt[val[st]] >= 2)) {
                if(val[st] <= K) --cnt[val[st]];
                ++st;
            }
            if(cnt.size() >= K) ans = min(ans, ed - st + 1);
        }
        if(ans == INT_MAX) printf("Case %d: sequence nai\n", ++kase);
        else printf("Case %d: %d\n", ++kase, ans);
    }
    return 0;
}

欢迎留言