首页 > 试题广场 >

小团的装饰物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$

算法知识视频讲解

看星星呐

n,m,k = map(int, input().split())
a = list(map(int, input().split()))
flag = 0
result = 0
for i in range(n):
    if a[i]>=k: flag += 1
    else: flag = 0
    if flag==m:
        result += 1
        flag = m-1
print(result)

发表于 2021-09-01 09:45:16 回复(0)

_叶知秋

采用滑动窗口的思想，但实际上不需要真实进行滑动的操作。

思路：存储排列中小于k的物品的所有下标，然后两个小于k的下标之间就是满足条件的物品，其长度和窗口长度比较，就可以直接算出该长度内有多少个满足窗口

注意：① pre初始化为-1；② 在数组最后加上一个下标n；③ 边界情况

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
             // 用这个读会比Scanner快很多
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]);
        int m = Integer.parseInt(params[1]);
        int k = Integer.parseInt(params[2]);
        params = br.readLine().trim().split(" ");
        int[] goods = new int[n];
        for(int i=0;i<n;++i){
            goods[i] = Integer.parseInt(params[i]);
        }
        System.out.println(buy(n,m,k,goods));
    }
    
    public static int buy(int n,int m,int k,int[] goods){
        if(m>n){
            return 0;
        }
        // 存储小于k的物品下标
        List<Integer> no = new ArrayList<>();
        for(int i=0;i<n;++i){
            if(goods[i]<k){
                no.add(i);
            }
        }
        if(no.size()==0){
            return n-m+1;
        }
        // 在最后加一个n，就不用单独考虑末尾的情况
        no.add(n);
        int cnt = 0;
        int pre = -1;
        for(int idx:no){
            // 在(pre,idx)内有len个满足的数
            int len = idx - pre - 1;
            // len个数中取连续的m个数
            if(len-m+1 > 0){
                cnt += len - m + 1;
            }
            pre = idx;
        }
        return cnt;
    }
}

编辑于 2022-03-05 13:45:04 回复(0)

苦逼的90后

滑动窗口小混一波

import java.util.Scanner;
 
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[] beauty=new int[n];
        for (int i = 0; i < n; i++) {
            beauty[i]=sc.nextInt();
        }
        int s=0,e=0,res=0;
        while (e<n-1){
            if (beauty[e]>=k){
                e++;
                if (beauty[e]>=k&&(e-s+1)==m){
                    res++;
                    s++;
                    e=s;
                }
            }else {
                e++;
                s=e;
            }
        }
        System.out.println(res);
    }
}

发表于 2021-06-01 21:21:47 回复(0)

Yingf

n,m,k=map(int,input().split())
a=[int(i) for i in input().split()]
is_beaty=[0]*n
for i in range(n):
    if a[i]>=k:
        is_beaty[i]=1
ans=0
num=0
for i in range(n):
    if is_beaty[i]==1:
        num+=1
    else:
        if num>=m:
            ans+=(num-m+1)
        num=0
if num!=0 and num>=m:
    ans+=(num-m+1)
print(ans)

发表于 2021-03-10 17:34:17 回复(1)

pein531

用小根堆构建一个长度为m的窗口，然后滑动窗口求解，如果堆顶元素大于等于k，方案数就+1。每次滑动窗口时将原来的左边界元素弹出，新的右边界元素压入。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]);
        int m = Integer.parseInt(params[1]);
        int k = Integer.parseInt(params[2]);
        params = br.readLine().trim().split(" ");
        int[] pretty = new int[n];
        for(int i = 0; i < n; i++)
            pretty[i] = Integer.parseInt(params[i]);
        int count = 0;
        // 构建一个小根堆作为窗口
        PriorityQueue<Integer> window = new PriorityQueue<>();
        // 滑窗遍历
        for(int left = 0; left <= n - m; left++){
            if(left == 0){
                // 构建初始窗口
                for(int i = left; i <= left + m - 1; i++)
                    window.offer(pretty[i]);
            }else{
                window.remove(pretty[left - 1]);
                window.offer(pretty[left + m - 1]);
            }
            // 这一段连续区间满足要求
            if(window.peek() >= k) count++;
        }
        System.out.println(count);
    }
}

发表于 2021-03-03 18:33:30 回复(0)

JCoder

单调队列的板题，滑动窗口最小/最大值

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
int a[100005];
int main() {
    scanf("%d%d%d", &n, &m, &k);
    int ans = 0;
    deque<int> q;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; i++) {
        while (!q.empty() && a[i] < a[q.back()]) {
            q.pop_back();
        }
        q.push_back(i);
        if (i >= m - 1 && a[q.front()] >= k) {
            ans += 1;
        }
        if (i - m + 1 == q.front()) {
            q.pop_front();
        }
    }
    printf("%d\n", ans);

    return 0;
}

发表于 2021-08-17 15:10:27 回复(0)

来自蓝星

// 阿这，看了大佬们的解析，不知道我这解法属于哪个门派。。。
#include <iostream>
#include <vector>
using namespace std;
int main() {
	int n, m, k;
	cin >> n >> m >> k;
	vector<int> vN(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> vN[i];
	}

	int res = 0;
    int length = 0;
	for (int i = 0; i < n; i++){
		if(vN[i] >= k) {
            length++;
        } else{
            length = 0;
        }
        if(length == m)  {
            res+=1;
            length--;
        }
	}
	cout << res;
    return 0;
}

发表于 2022-09-17 08:55:38 回复(0)

开心是种能力

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] str1 = in.nextLine().split(" ");
        String[] str2 = in.nextLine().split(" ");
        int n = Integer.parseInt(str1[0]);
        int m = Integer.parseInt(str1[1]);
        int k = Integer.parseInt(str1[2]);
        int[] beauty = new int[n];
        for (int i = 0; i < str2.length; i++) {
            beauty[i] = Integer.parseInt(str2[i]);
        }
        int start = 0, index = 0, res = 0;
        while (index < beauty.length) {
            if (beauty[index] < k) {
                start = index + 1;
                index++;
                continue;
            }
            if (index - start + 1 == m) {
                res++;
                start++;
            }
            index++;
        }
        System.out.print(res);
    }
}

这题直接双指针法也挺香的

发表于 2022-08-30 10:32:45 回复(0)

咚呱呱

直接求一段都大于k的长度l，那么l-k+1就是这一段中包含的答案个数。 O（n）

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] nums = sc.nextLine().split(" ");
        int n = Integer.parseInt(nums[0]);
        int m = Integer.parseInt(nums[1]);
        int k = Integer.parseInt(nums[2]);
        int ans = 0;
        int[] num = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
        if (n < m) System.out.println("0");
        else {
            int count = 0;
            for (int i = 0; i < n; i++){
                if (num[i] >= k) {
                    count++;
                } else {
                    ans += count >= m ? count - m + 1 : 0;
                    count = 0;
                }
            }
            ans += count >= m ? count - m + 1 : 0;
            System.out.println(ans);
        }
    }
     
}

发表于 2022-08-20 09:29:38 回复(0)

牛客833845976号

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[] arr = new int[n];
        
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int count = 0;
        int num = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] >= k) {
                for (; i < n; i++) {
                    if (arr[i] >= k) {
                        num++;
                    }else {
                        break;
                    }
                }
            }
            
            if (num >= m) {
                count += num-m+1;
            }
            num = 0;
        }
        
        System.out.println(count);
    }
}

发表于 2022-07-29 17:14:16 回复(0)

wonderson

import java.util.*;
    public class Main {
        public static void main(String[] args) {

            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = sc.nextInt();
            }
            sc.close();
            int tmp = m;
            int cnt = 0;
            int sum = 0;

            int lo = 0, hi = 0;
            loop: while (hi < n) {
                while (hi < n) {
                    if (nums[hi] < k) {
                        sum = 0;
                        m = tmp;
                        lo = hi = hi + 1;
                        continue loop;
                    }
                    sum += nums[hi];
                    hi++;
                    m--;
                    if (m == 0) {
                        break;
                    }
                }
                if (m == 0) {
                    // System.out.println((lo + 1)+ " " + (hi) + " " + " " + sum);
                    cnt++;
                }
                sum -= nums[lo++];
                m++;
            }
            System.out.println(cnt);
        }
    }

发表于 2022-04-12 18:30:17 回复(0)

只想拿个offer啊

滑动窗口最小值, 用单调队列或优先队列(堆)均可.

单调队列的时间复杂度为O(n), 优先队列的时间复杂度为O(nlogn)

#include <bits/stdc++.h>

using namespace std;

void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> nums(n, 0);

    for (int i = 0; i < n; i ++ )
        cin >> nums[i];
    deque<int> dq;
    int ans = 0;
    for (int i = 0; i < n; i ++ ) {
        if (dq.size() and i >= dq.front() + m)
            dq.pop_front();
        while (dq.size() and nums[dq.back()] >= nums[i])
            dq.pop_back();
        dq.push_back(i);
        if (i >= m - 1)
            ans += nums[dq.front()] >= k;    
    }
    cout << ans <<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    // cin >> t;
    t = 1;
    while (t -- )
        solve();
    return 0;
}

我们观察到只需要统计滑动窗口内满足条件的数的个数即可，而满足不与不满足可以用1和0表达, 因此将原问题转化成区间和问题, 可以使用前缀和技巧O(1)获得滑动窗口的区间和, 整体时间复杂度为O(n).

实现中无需预处理出前缀和数组, 直接使用变量s动态维护滑动窗口内的和即可

#include 
using namespace std;
void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    vector nums(n, 0);
    for (int i = 0; i < n; i ++ )
        cin >> nums[i];
    int ans = 0;
    for (int i = 0, s = 0; i < n; i ++ ) {
        if (i >= m)
            s -= nums[i - m] >= k;
        s += nums[i] >= k;
        if (s == m)
            ans ++ ; 
    }
    cout << ans <<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    // cin >> t;
    t = 1;
    while (t -- )
        solve();
    return 0;
}

编辑于 2021-10-18 14:17:53 回复(0)

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)

Python

maoxiaomao

本来想滑动窗口的，后来感觉队列好像还更简单一些...

import collections 
n,m,k=map(int, input().strip().split())
A=list(map(int, input().strip().split()))
q=collections.deque() 
ans=[]
for i in range(len(A)):
    if A[i]>=k:  #入队
        q.append(i+1)
        if len(q)==m:   #队满
            tmp=list(q) 
            ans.append(tmp[0:m+1])
            q.popleft() 
    else:        #出队
        while q:
            q.popleft()
print(len(ans))

发表于 2021-08-06 14:12:12 回复(0)

牛客69652187号

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[] goods = new int[n];
        for(int i = 0; i < n; i++){
            goods[i] = sc.nextInt();
        }sc.close();
         
        int count = 0;
        for(int i = 0; i < n-m+1; i++){
            for(int a = i; a < m+i; a++){
                if(goods[a] < k){
                    count++;
                    break;
                }
            }
        }
        System.out.println(n-m+1-count);
    }
}

减法

发表于 2021-04-24 17:57:22 回复(0)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师美团前端工程师算法工程师 2021 大数据开发工程师 Java工程师

上传者：小小

难度：

16条回答 22收藏 2958浏览

通过挑战的用户

SikaSilva

2023-03-13 14:58:24
牛客85284...

2023-03-11 10:01:28
2023/2/22

2023-03-08 21:46:21
尤里组长

2022-11-17 21:02:08
勤劳的猕猴桃在攒经验

2022-11-12 10:09:40