小团的装饰物2

[编程题]小团的装饰物2

热度指数：1799 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小团需要购买m样装饰物。商店出售n种装饰物，按照从小到大的顺序从左到右摆了一排。对于每一个装饰物，小团都给予了一个美丽值 $a_i$ 。

小团希望购买的装饰物有着相似的大小，所以他要求购买的装饰物在商店中摆放的位置是连续的一段。小团还认为，一个装饰物的美丽值不能低于k，否则会不好看。

现在，请你计算小团有多少种不同的购买方案。

输入描述:

输入第一行包含三个数n, m, k

接下来一行n个数 $a_i(1\leq i\leq n)$ ，空格隔开，表示商店从左到右摆放的每个装饰物的美丽值。

输出描述:

输出一个数，表示小团购买的方案数。

示例1

输入

8 2 5
5 5 5 4 5 5 5 5

输出

说明

有[1,2][2,3][5,6][6,7][7,8] 共5段

备注:

对于40%的数据， $n, m\leq 100$

对于100%的数据， $n, m\leq 100000, 1\leq a_i, k\leq 10^9$

算法知识视频讲解

Java

hiahia#

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner stdin = new Scanner(System.in);
        int n = stdin.nextInt();
        int m = stdin.nextInt();
        int k = stdin.nextInt();
        int splitPoint=-1;
        int t = 0;
        int total= 0;
        // 按不满足要求的点分割，分割后若某段长度为len中全是满足要求的，
        // 则该段组合数为len-m+1
        for(int i = 0;i<n;++i){
           t = stdin.nextInt();
           if(t<k){
               //System.out.println("i="+i+",total="+total);
               int len =  (i-splitPoint-1);
               total+= (len>=m)?( len-m+1):0;
               splitPoint=i;
           }
       }
        //System.out.println("i="+(n)+",total="+total);
        int len =  (n-splitPoint-1) ;
        total+= (len>=m)?( len-m+1):0;
        //System.out.println("total="+total);
        System.out.println(total);
        
    }
}

甚至不需要数组

发表于 2021-09-10 20:41:06 回复(0)

Java

牛客659183249号

import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int []a = new int[n];
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        int res = 0;
        int count = 0;
        for(int i=0;i<m;i++){
            if(a[i]<k)count++;
        }
        if(count==0)res++;
        for(int end=m;end<n;end++){
            int begin=end+1-m;
            if(a[end]<k)count++;
            if(a[begin-1]<k)count--;
            if(count==0)res++;
        }
        System.out.println(res);
    }
}
记录下不满足要求的次数，如果为0，答案+1

发表于 2021-08-19 22:22:58 回复(0)