小D是一名老师,他想选出一些同学参加一个团体比赛。
总共有n个同学,每个同学有一个能力值x和一个合作值y,小D将这些同学排成一排。
选人的规则如下:小D将选择一排中连续的k个同学参加比赛,而且为了保证比赛成绩,这k个同学的能力值不能小于a,合作值不能小于b。小D想知道总共有多少种可能的选人方案。
第一行四个正整数n,k,a,b。
第二行n个通过空格隔开的正整数表示一排n个同学的能力值。
第二行n个通过空格隔开的正整数表示一排n个同学的合作值。
n <= 80000,
保证k<=n且x,y,a,b<=100000。
输出一个非负整数表示选人方案数。
10 2 2 4 2 2 9 1 8 1 6 1 7 7 4 8 5 1 9 4 1 3 9 4
3
有选择第1,2两个人,第2,3两个人,第9,10两个人三种方案。
#include <stdio.h>
#include <stdbool.h>
int main() {
int n, k, a, b;
scanf("%d %d %d %d", &n, &k, &a, &b);
int abilityValue[n];
int cooperationValue[n];
for (int i = 0; i < n; i++) {
scanf("%d", &abilityValue[i]);
}
for (int i = 0; i < n; i++) {
scanf("%d", &cooperationValue[i]);
}
bool canSelect[n];
for (int i = 0; i < n; i++) {
canSelect[i] = false;
}
for (int i = 0; i < n - k + 1;) {
if (i == 0 || !canSelect[i - 1]) {
int j = i;
for (; j < i + k; j++) {
if (abilityValue[j] < a || cooperationValue[j] < b) {
i = j + 1;
break;
}
}
if (j == i + k) {
canSelect[i] = true;
i += 1;
}
} else {
int j = i + k - 1;
if (abilityValue[j] < a || cooperationValue[j] < b) {
i = j + 1;
} else {
canSelect[i] = true;
i += 1;
}
}
}
int r = 0;
for (int i = 0; i < n - k + 1; i++) {
if (canSelect[i]) {
r += 1;
}
}
printf("%d\n", r);
return 0;
}