[滑动窗口] UVa11536 最小子序列 (二分滑窗长度)
程序员文章站
2022-03-11 19:58:16
...
题目
思路
这题就很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;
}