塔子哥的最短区间-小米2023笔试(codefun2000)

题目链接
塔子哥的最短区间-小米2023笔试(codefun2000)

题目内容

塔子哥有一个长度为 n 的数组 a 和 长度为 m 的数组 b ，下标均从 1 开始。
现在，塔子哥想让你找出一个最短的区间 l,r ， 这个区间中数 x 的数量至少出现了 b[x] 次。

输入描述

第一行，两个整数 n,m($1\le n,m\le 10^5$ ) 分别表示数组 a 和数组 b 的长度。
第二行，n 个整数表示数组 a 。
第三行，m 个整数表示数组 b 。

输出描述

一个整数，表示最短区间的长度，如果不存在，则输出 -1 。

样例1

输入

6 4
1 1 4 5 1 4
2 0 0 2

输出

5

提示

区间 [2,6] 满足 1 和 4 出现了至少两次，2 和 3 出现了至少 0 次。 可以证明没有更短的区间满足了。

题解1

#include<bits/stdc++.h> using namespace std;  const int N = 1e5 + 10;  int n, m, a[N], b[N], cnt[N]; // cnt[i]表示i出现的次数   bool check(int x){ // 当前枚举的区间长度为x  	memset(cnt, 0, sizeof cnt); 	for(int i = 1; i <= n; i++){  		cnt[a[i]]++;// 双指针 		if(i >= x){   			int j = 1; 			while(j <= m && cnt[j] >= b[j]) j++; 			if(j > m) return true; 			cnt[a[i - x + 1]]--; 		} 	} 	return false; } int main(){ 	scanf("%d%d", &n, &m); 	for(int i = 1; i <= n; i++) scanf("%d", &a[i]); 	for(int i = 1; i <= m; i++) scanf("%d", &b[i]); 	 	int left = - 1, right = n + 1, mid; 	while(left + 1 < right){ // 二分枚举满足条件的最小区间的长度  		mid = (left + right)/2; 		if(check(mid)) right = mid; 		else left = mid; 	} 	printf("%d\n", check(right)?right:-1); 	return 0; }