首页 > 试题广场 >

排队选人

[编程题]排队选人
  • 热度指数：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两个人三种方案。

备注:

算法知识视频讲解
查看答案及解析
添加回答
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)
YUANDK头像 YUANDK 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int a = in.nextInt();
        int b = in.nextInt();
        int[] arrX = new int[n];
        int[] arrY = new int[n];
        for (int i = 0; i < n; i++) {
            arrX[i] = in.nextInt();
        }
        for (int i = 0; i < n; i++) {
            arrY[i] = in.nextInt();
        }
        int left = 0;
        int right = k - 1;
        int countK = 0;
        int count = 0;
        for (int i = left; i <= right; i++) {
            if (arrX[i] >= a && arrY[i] >= b) {
                countK++;
            }
        }
        if (countK == k) count++;
        left++;
        right++;

        while (right < n) {
            if (arrX[left - 1] >= a && arrY[left - 1] >= b) {
                countK--;
            }
            if (arrX[right] >= a && arrY[right] >= b) {
                countK++;
            }
            if (countK == k) count++;
            left++;
            right++;
        }
        System.out.println(count);
    }
}

发表于 2025-08-28 11:03:26 回复(0)
JavaScript Node
枯木逢春只醉看头像 枯木逢春只醉看
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    let count=0,n,k,a,b,aList,bList,flag=0
    while(line = await readline()){
        let input = line.split(' ').map(item=>parseInt(item))
        if(flag==0){
            n = input[0]
            k= input[1]
            a = input[2]
            b = input[3]
            flag++
        }else if(flag==1){
            aList = input
            flag++
        }else{
            bList = input
            flag++
        }
    }
    for(let i=0;i<n;i++){
        let t = 0
        while(t<k){
            if(aList[i+t]>=a && bList[i+t]>=b){
                t++
            }else{
                break
            }
        }
        if(t==k){
            count++
        }
    }
    console.log(count)
}()

发表于 2025-12-10 15:59:19 回复(0)
云淡_风轻头像 云淡_风轻
publicstaticvoidmain(String[] args) {
        Scanner in = newScanner(System.in);
         
        // 注意 hasNext 和 hasNextLine 的区别
        while(in.hasNextLine()) { // 注意 while 处理多个 case
            String[] str = in.nextLine().trim().split(" ");
            intn = Integer.parseInt(str[0]);
            intk = Integer.parseInt(str[1]);
            inta = Integer.parseInt(str[2]);
            intb = Integer.parseInt(str[3]);
            String[] strx = in.nextLine().trim().split(" ");
            String[] stry = in.nextLine().trim().split(" ");
            int[] flag = newint[n];
            for(inti = 0; i < n; i++) {
                intx = Integer.parseInt(strx[i]);
                inty = Integer.parseInt(stry[i]);
                if(x >= a && y >= b) {
                    flag[i] = 1;
                }
            }
 
            intsum = 0;
            intnum = 0;
            for(inti = 0; i < k; i++) {
                if(flag[i] == 0) {
                    num++;
                }
            }
            if(num == 0) {
                sum += 1;
            }
            for(inti = k; i < n; i++) {
                if(flag[i - k] == 0) {
                    num--;
                }
                if(flag[i] == 0) {
                    num++;
                }
                if(num == 0) {
                    sum += 1;
                }
            }
 
            System.out.println(sum);
        }
    }
发表于 2025-11-21 17:51:20 回复(0)
nightcherry头像 nightcherry 
import java.util.Scanner;
 
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        int start = -1;
 
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt(), k = in.nextInt(), a = in.nextInt(), b=in.nextInt();
        int[] aArr = new int[n]; int[] bArr = new int[n];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            aArr[i] = in.nextInt();
        }
        for (int i = 0; i < n; i++) {
            bArr[i] = in.nextInt();
        }
        for (int i = 0; i < n; i++) {
            if(aArr[i] >= a && bArr[i] >= b){
                if(start == -1){
                    start = i;
                    //System.out.println("start:"+start);
                }
            }else{
                if(start != -1){
                    int end = i - 1;
                    //System.out.println("end:"+end);
                    if((end - start + 1) >= k){
                        cnt += (end - start + 1) - k + 1;
                    }
                    start = -1;
                }
            }
        }
        if(start != -1){
            cnt += (n - 1 - start + 1) - k + 1;
        }
        System.out.println(cnt);
    }
}
假设有区间 0 ～ 2符合，那么该区间长度为l = 3, 则有 l - k + 1个组合，将其加到cnt中，问题解决。
发表于 2025-10-09 16:36:26 回复(0)
Java
comfound头像 comfound 
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[] as=new int[n]; int[] bs=new int[n]; int sum=0; for (int i=0;i<n;i++){
        as[i]=sc.nextInt();
    } for (int i=0;i<n;i++){
        bs[i]=sc.nextInt();
    } for (int i=0;i<=n-k;i++){ int lag=0; for(int j=i;j<k+i;j++){ if (as[j]<a||bs[j]<b){ break;
            }else {
                lag++;
            }
        } if (lag==k){
            sum++;
        }
    }
    System.out.println(sum);

}
发表于 2025-09-22 14:05:03 回复(0)
Java
多多秋招offer头像 多多秋招offer 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int a = in.nextInt();
        int b = in.nextInt();
        int[] arrX = new int[n];
        int[] arrY = new int[n];
        for (int i = 0; i < n; i++) {
            arrX[i] = in.nextInt();
        }
        for (int i = 0; i < n; i++) {
            arrY[i] = in.nextInt();
        }

        int count = 0;

        int [] pre = new int[n+1];
        for(int i=1;i<=n;i++){
            if (arrX[i-1] >= a && arrY[i-1] >= b) {
                pre[i]=pre[i-1]+1;
            }else{
                pre[i]=pre[i-1];
            }
        }
        for(int i=k;i<=n;i++){
            if(pre[i]-pre[i-k]==k){
                count++;
            }
        }
        System.out.println(count);
    }
}

发表于 2025-09-20 15:28:53 回复(0)
C
syuctzxk头像 syuctzxk 
#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)
牛客723899313号头像 牛客723899313号

#include <iostream>

#include <numeric>

#include <vector>

#include <sys/types.h>

using namespace std;


int main() {

// int a, b;

// while (cin >> a >> b) { // 注意 while 处理多个 case

// cout << a + b << endl;

// }

int n,k;

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

vector<int> nengli_hezuo(n,1); // 1表示达标，0表示不符要求

int temp;

for(int i = 0;i<n;i++)

{

cin>>temp;

if(temp<a)nengli_hezuo[i] = 0;

}

for(int i = 0;i<n;i++)

{

cin>>temp;

if(temp<b)nengli_hezuo[i] = 0;

}

int ans = 0,sum = accumulate(nengli_hezuo.begin(),nengli_hezuo.begin()+k,0);

if(sum == k) ans++;

for(int i = k;i<n;i++)

{

sum = sum+nengli_hezuo[i] - nengli_hezuo[i-k];

if(sum == k) ans++;

}

cout<<ans;

}

// 64 位输出请用 printf("%lld")


发表于 2025-08-20 21:06:07 回复(0)
提交观点

问题信息

数组 小米集团 双指针
难度：
9条回答 1023浏览

热门推荐

相关试题

排队选人

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号