首页 > 试题广场 >

排队选人

[编程题]排队选人

热度指数：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

输出

说明

有选择第1,2两个人，第2,3两个人，第9,10两个人三种方案。

备注:

算法知识视频讲解

查看答案及解析

Python

爪特猫

import sys

# 读取第一行输入数据：n, k, a, b
g_data = list(map(int, sys.stdin.readline().split()))
n = g_data[0]  # 学生总数
k = g_data[1]  # 需要选择的连续学生数
a = g_data[2]  # 能力值下限
b = g_data[3]  # 合作值下限

# 读取能力值数组和合作值数组
nums1 = list(map(int, sys.stdin.readline().split()))  # 能力值
nums2 = list(map(int, sys.stdin.readline().split()))  # 合作值

count = 0  # 记录当前连续满足条件的学生数
ans = 0    # 记录总方案数

# 遍历每个学生
for i in range(n):
    # 如果当前学生同时满足能力值和合作值要求，连续计数+1
    if nums1[i] >= a and nums2[i] >= b:
        count += 1
    else:
        # 不满足条件则重置连续计数
        count = 0
    
    # 当连续满足条件的学生数达到k时，方案数+1，同时连续计数-1（为了处理重叠窗口）
    if count == k:
        ans += 1
        count -= 1

# 输出结果
print(ans)

这题很好做

发表于 2025-09-24 22:19:11 回复(1)