题解 | #排队选人#

题目链接

排队选人

题目描述

总共有 $n$ 个同学排成一排，每个同学有两个属性：能力值 $x$ 和合作值 $y$ 。

需要从中选出连续的 $k$ 个同学，同时要求这 $k$ 个同学中，每个人的能力值都不小于 $a$ ，合作值都不小于 $b$ 。

求解总共有多少种满足条件的选人方案。

解题思路

这是一个简单的滑动窗口或线性扫描问题。我们的目标是找到所有长度为 $k$ 的连续子数组，其中每一个元素都满足给定的双重条件。

1. 简化问题

我们可以将问题分解为两个步骤：

首先，判断每个同学是否“合格”。一个同学是合格的，当且仅当他的能力值不小于 $a$ 并且合作值不小于 $b$ 。
然后，在由“合格”/“不合格”组成的序列中，统计有多少个长度为 $k$ 的、全部由“合格”组成的连续子段。

2. 线性扫描与计数

我们可以通过一次遍历来解决这个问题。维护一个计数器 consecutive_qualified，用来记录当前已经连续了多少个合格的同学。

我们从左到右遍历每一位同学。
对于第 $i$ 位同学，检查他的能力值和合作值。
- 如果他合格（能力值 $\ge a$ 且合作值 $\ge b$ ），我们就将 consecutive_qualified 加 1。
- 如果他不合格，那么连续的合格序列就被中断了，我们必须将 consecutive_qualified 重置为 $0$ 。
在每次更新 consecutive_qualified 后，我们检查它的值。如果 consecutive_qualified >= k，这意味着我们找到了一个以当前同学为结尾的、长度为 $k$ 的合格队伍。因此，我们将总方案数加 1。

例如，假设 $k=3$ ，一个合格序列的 consecutive_qualified 变化如下： ...0, 1, 2, 3, 4, 5, 0, ...

当 consecutive_qualified 变为 3 时，我们找到了第一个方案 [1,2,3]。
当 consecutive_qualified 变为 4 时，我们找到了第二个方案 [2,3,4]。
当 consecutive_qualified 变为 5 时，我们找到了第三个方案 [3,4,5]。

遍历完所有同学后，累加的方案数即为最终答案。

代码

cpp
java
python

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k, a, b;
    cin >> n >> k >> a >> b;

    vector<int> abilities(n);
    vector<int> cooperations(n);

    for (int i = 0; i < n; ++i) cin >> abilities[i];
    for (int i = 0; i < n; ++i) cin >> cooperations[i];

    long long total_schemes = 0;
    int consecutive_qualified = 0;

    for (int i = 0; i < n; ++i) {
        if (abilities[i] >= a && cooperations[i] >= b) {
            consecutive_qualified++;
        } else {
            consecutive_qualified = 0;
        }

        if (consecutive_qualified >= k) {
            total_schemes++;
        }
    }

    cout << total_schemes << endl;

    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();
        int k = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();

        int[] abilities = new int[n];
        int[] cooperations = new int[n];

        for (int i = 0; i < n; i++) {
            abilities[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            cooperations[i] = sc.nextInt();
        }

        long totalSchemes = 0;
        int consecutiveQualified = 0;

        for (int i = 0; i < n; i++) {
            if (abilities[i] >= a && cooperations[i] >= b) {
                consecutiveQualified++;
            } else {
                consecutiveQualified = 0;
            }

            if (consecutiveQualified >= k) {
                totalSchemes++;
            }
        }

        System.out.println(totalSchemes);
    }
}

import sys

def main():
    try:
        line = sys.stdin.readline()
        if not line:
            return
        n, k, a, b = map(int, line.split())
        
        abilities = list(map(int, sys.stdin.readline().split()))
        cooperations = list(map(int, sys.stdin.readline().split()))
        
        total_schemes = 0
        consecutive_qualified = 0
        
        for i in range(n):
            if abilities[i] >= a and cooperations[i] >= b:
                consecutive_qualified += 1
            else:
                consecutive_qualified = 0
            
            if consecutive_qualified >= k:
                total_schemes += 1
                
        print(total_schemes)

    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

算法及复杂度

算法：线性扫描 / 滑动窗口
时间复杂度：我们只需要对输入的 $n$ 个同学进行一次遍历，因此时间复杂度为 $O(n)$ 。
空间复杂度：除了存储输入的两个数组外，我们只需要常数个额外变量来维护状态。因此，额外空间复杂度为 $O(1)$ 。总空间复杂度为 $O(n)$ 。