首页 > 试题广场 >

排队选人

[编程题]排队选人
  • 热度指数:1483 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小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。


输出描述:
输出一个非负整数表示选人方案数。
示例1

输入

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;
}

发表于 2025-08-28 00:32:59 回复(0)