排队选人
排队选人
https://www.nowcoder.com/practice/8f526def031f43b49d54e71117f6d990
排队选人
[题目链接](https://www.nowcoder.com/practice/8f526def031f43b49d54e71117f6d990)
思路
从 个同学中选出连续
个，要求每个人的能力值
、合作值
，求方案数。
标记与连续计数
先对每个同学判断是否"合格"（能力值 且合作值
）。问题转化为：在一个
序列中，有多少个长度为
的子段全为
。
只需维护一个计数器 ，记录当前位置为止连续合格同学的个数：
- 若第
个同学合格，
；
- 否则
。
每当 ，就找到了一个合法方案（以第
个同学为结尾的连续
人）。
样例验证
能力值 [2,2,9,1,8,1,6,1,7,7]，合作值 [4,8,5,1,9,4,1,3,9,4]，。
合格序列为 [1,1,1,0,1,0,0,0,1,1]，连续段为 [1,2,3]、[5]、[9,10]。长度 的窗口个数：
。
复杂度
- 时间：
- 空间：
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, k, a, b;
scanf("%d%d%d%d", &n, &k, &a, &b);
vector<int> x(n), y(n);
for(int i = 0; i < n; i++) scanf("%d", &x[i]);
for(int i = 0; i < n; i++) scanf("%d", &y[i]);
int ans = 0, cnt = 0;
for(int i = 0; i < n; i++){
if(x[i] >= a && y[i] >= b) cnt++;
else cnt = 0;
if(cnt >= k) ans++;
}
printf("%d\n", ans);
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt(), a = sc.nextInt(), b = sc.nextInt();
int[] x = new int[n], y = new int[n];
for(int i = 0; i < n; i++) x[i] = sc.nextInt();
for(int i = 0; i < n; i++) y[i] = sc.nextInt();
int ans = 0, cnt = 0;
for(int i = 0; i < n; i++){
if(x[i] >= a && y[i] >= b) cnt++;
else cnt = 0;
if(cnt >= k) ans++;
}
System.out.println(ans);
}
}
查看16道真题和解析