网站建设课后感搜外友链

登录—专业IT笔试面试备考平台_牛客网

题目大意：给出一长度为n的仅由1,2,3,4组成的数组和一整数k，求一个最短的区间使得1,2,3,4至少各有一个，且4的数量>=k

1<=k<=n<=1e5

思路：用双指针l，r维护合法区间，先向右扩展r，同时记录访问过几个不同的数以及4的数量直到满足要求，然后缩短左端点l，维护当前区间内每个数的个数，直到不满足条件就记录答案

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int INF = 0x7fffffff;
int a[N];
int vis[5];
int main()
{ios::sync_with_stdio(false);cin.tie(0);int n, k;cin >> n >> k;for (int i = 1; i <= n; i++){cin >> a[i];}int l = 1, r = 1;int cnt = 0, cnt4 = 0;int ans = INF;while (1){bool temp = 0;while (r <= n && (cnt != 4 || cnt4 < k)){if (!vis[a[r]])cnt++;vis[a[r]]++;if (a[r] == 4)cnt4++;r++;}while(cnt==4&&cnt4>=k){		temp = 1;vis[a[l]]--;if (!vis[a[l]])cnt--;if (a[l] == 4)cnt4--;l++;}if (temp){ans = min(ans, r - l + 1);}elsebreak;}cout << ans << endl;return 0;
}