欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[滑动窗口] UVa11536 最小子序列 (二分滑窗长度)

程序员文章站 2022-03-11 19:58:16
...

题目

[滑动窗口] UVa11536 最小子序列 (二分滑窗长度)

思路

这题就很easy了,了解一下二分滑窗长度的方法为主要。
1.根据题目给的公式,算出整个A[i]。
2.由于滑窗长度的解存在单调性,具体来说是若L = a时不成立,L=b时成立,那解必然在(a,b]中。所以用二分查找查找解,然后根据滑窗长度遍历一遍,此处的遍历有点像Shuffle那道题

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#define _rep(i,a,b) for(int i = (a); i<=(b); i++)

const int maxn = 1000000 + 1000;
int n, m, k, A[maxn];

// 用长度为t的滑窗尝试
bool solve(int t) {
    int tot = 0, cnt[1000 + 50];  //tot:存在于滑窗的小于等于k的元素的个数,cnt[i]:i在滑窗中个数
    memset(cnt, 0, sizeof(cnt));
    _rep(i, 1, n) {
        if (tot == k) return true;
        if (i == n) break;  //防止超下标访问
        if (A[i + 1] <= k && cnt[A[i + 1]]++ == 0) tot++;
        if (i > t && A[i - t + 1] <= k && --cnt[A[i - t + 1]] == 0) tot--;
    }
    return false;
}

int main() {
    int T, kase = 0;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &k);
        A[1] = 1; A[2] = 2; A[3] = 3;
        _rep(i, 4, n) A[i] = (A[i - 1] + A[i - 2] + A[i - 3]) % m + 1;

        // 二分滑窗长度
        int L = 1, R = n + 1;
        while (L < R) {
            int M = L + (R - L) / 2;
            if (solve(M)) R = M;
            else L = M+1;
        }
        if (solve(L)) printf("Case %d: %d\n",++kase, L);
        else printf("Case %d: sequence nai\n",++kase);
    }

    return 0;
}