首页 > 试题广场 >

数组计数维护

[编程题]数组计数维护
  • 热度指数：1428 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定正整数 n 和阈值 k 以及长度为 n 的整数序列 \{a_1,a_2,\dots,a_n\}。
\hspace{15pt}你需要动态地维护两个正整数变量 S 和 cnt，初始时，S=cnt=0。
\hspace{15pt}按照从 1 到 n 的顺序，对每个下标 i 执行：
\hspace{23pt}\bullet\,若 a_i \ge k，则 S \leftarrow S + a_i；
\hspace{23pt}\bullet\,若 a_i = 0 且 S \ge 1，则 S \leftarrow S - 1 且 cnt \leftarrow cnt + 1；
\hspace{23pt}\bullet\,否则，不进行任何操作。
\hspace{15pt}输出最终 cnt 的值。

输入描述:
\hspace{15pt}第一行输入一个整数 T\left(1\leqq T\leqq 10^4\right)，表示测试用例组数。
\hspace{15pt}每组测试用例格式如下：
{<br />\hspace{20pt}}_\texttt{1.}\,第一行输入两个整数 n,k\ \left(1\leqq n\leqq 50;\ 1\leqq k\leqq 100\right)；
{<br />\hspace{20pt}}_\texttt{2.}\,第二行输入 n 个整数 a_1,a_2,\dots,a_n\ \left(0\leqq a_i\leqq 100\right).


输出描述:
\hspace{15pt}对于每组测试用例，输出一行一个整数，表示 cnt 的值。
示例1

输入

3
3 2
2 0 1
4 1
0 0 0 0
5 3
3 0 0 4 0

输出

1
0
3

说明

\hspace{15pt}对于第一组数据：
\hspace{23pt}\bullet\,n=3,k=2,a=[2,0,1]，第 1 项 2 \ge 2，S=2；第 2 项为 0，S\ge1，赠出 1 枚，cnt=1；第 3 项无操作；因此 cnt=1。
\hspace{15pt}对于第三组数据：
\hspace{23pt}\bullet\,n=5,k=3,a=[3,0,0,4,0]，第 1 项 3\ge3，S=3；第 2,3 项各赠出 1 枚，cnt=2,S=1；第 4 项 4\ge3，S=5；第 5 项再赠出 1 枚，cnt=3；因此 cnt=3。
算法知识视频讲解
添加回答
cross_sunny头像 cross_sunny 
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T --) {
        int n,k;
        cin >> n >> k;
        
        vector<int> v(n);
        int S = 0,cnt = 0;

        for (int &num : v) {
            cin >> num;
            if (num >= k) {
                S += num;
            }
            else if (num == 0 && S >= 1) {
                S--;
                cnt ++;
            }
        }

        cout << cnt << endl;
    }
}

发表于 2025-07-15 15:24:05 回复(0)
C
豆花饭ac头像 豆花饭ac
#include<stdio.h>
int main()
{
    int t,a[1001];
    scanf("%d",&t);
    while(t)
    {
        t--;
        int n,k;
        int s=0,cnt=0;
        scanf("%d %d",&n,&k);
        for(int i=0;i<n;i++)
        {
           
            scanf("%d",&a[i]);
            if(a[i]>=k)
            {
                s=s+a[i];
               
            }
            if(a[i]==0&&s>=1)
            {
                s=s-1;
                cnt = cnt+1;
            }
        }
        printf("%d\n",cnt);
    }
}
发表于 2025-07-19 17:26:50 回复(0)
牛客940035856号头像 牛客940035856号
t = int(input())
for j in range(t):
    n , k = map(int , input().split())
    a = list(map(int,input().split()))

    s=cnt=0
    for i in range(n):
        if a[i] >= k :
            s += a[i]
        elif a[i]==0 and s>= 1:
            s -=1
            cnt += 1
        else:
            pass
    print(cnt)
发表于 2025-07-18 16:35:48 回复(0)
摆烂了的小章鱼很想去东北泡澡头像 摆烂了的小章鱼很想去东北泡澡
T =  int(input())

for i in range(T):
    n,k = map(int,input().split(" "))  
    a = list(map(int,input().split(" ")))
    S = 0
    cnt = 0
    for j in range(len(a)):
        if a[j] >= k :
            S = S +a[j]
        elif (a[j] == 0) and (S >= 1):
            S = S-1
            cnt += 1
    print(cnt)

发表于 2025-07-17 10:04:11 回复(0)
C++
追风的羽汀头像 追风的羽汀 
#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    int S = 0, cnt = 0;
    for (int num : a) {
        if (num >= k) {
            S += num;
        } else if (num == 0 && S >= 1) {
            S -= 1;
            cnt += 1;
        }
    }
    
    cout << cnt << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        solve();
    }
    
    return 0;
}

发表于 2025-07-15 15:51:23 回复(0)
Python3
LI005头像 LI005
T = int(input())

for t in range(T):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    S = 0
    cnt = 0

    for i in range (n):
        if a[i] >= k:
            S = S + a[i]
        elif (a[i] == 0) and (S >= 1):
            S = S - 1
            cnt =cnt + 1
           
    print(cnt)
发表于 2025-07-15 05:39:42 回复(0)
C
练习时长两年半的鸽子很有趣头像 练习时长两年半的鸽子很有趣
#include <stdio.h>
#define NUM 100
int main() {
    int t = 0, n = 0, k = 0, cnt, s;
    int i, j;
    int a[NUM];
    scanf("%d", &t);
    for (i = 0; i < t; i++) {
        s = 0;
        cnt = 0;
        scanf("%d %d", &n, &k);
        for (j = 0; j < n; j++) {
            scanf("%d", &a[j]);
            if (a[j] >= k) {
                s += a[j];
            }
            if (a[j] == 0 && s >= 1) {
                s--;
                cnt++;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}
发表于 2025-07-14 22:58:20 回复(0)
牛客988118991号头像 牛客988118991号
a1 = int(input())
for i in range(0,a1):
    S=0
    cnt=0
    n,k=map(int,input().split())
    q=list(map(int,input().split()))
    for w in q:
        if w >= k:
            S=S+w
        elif w == 0 and S>=1:
            S=S-1
            cnt+=1
        else:
            pass
    print(cnt)
发表于 2025-07-14 21:37:22 回复(0)
Python3
精致的熊熊在努力存钱头像 精致的熊熊在努力存钱
T = int(input())
for t in range(T):
    n,k = map(int,input().split())
    li = list(map(int,input().split()))
    s = 0
    cnt = 0
    for i in li:
        if i >= k:
            s += i
        elif i == 0 and s>=1:
            s -= 1
            cnt += 1
        else:
            pass
    print(cnt)

发表于 2025-07-12 23:40:19 回复(0)
C
牛客146476420号头像 牛客146476420号 
#include <stdio.h>

int main() 
{
    int T=0;
    int i=0;
    scanf("%d",&T);
    int S=0,cnt=0;
    for(i=0;i<T;i++)
    {
        int n=0;
        int k=0;
        scanf("%d %d",&n,&k);
        int arr[50]={0};
        int j=0;
        for(j=0;j<n;j++)
        {
            scanf("%d",&arr[j]);
            if(arr[j]>=k)
            {
                S=S+arr[j];
            }
            if(arr[j]==0&&S>=1)
            {
                S=S-1;
                cnt=cnt+1;
            }
        }
        printf("%d\n",cnt);
        cnt=0;//置0
        S=0;
    }

    return 0;
}

发表于 2025-07-11 16:27:49 回复(0)
Go
小明白头像 小明白 
package main

import (
	"fmt"
)

func main() {
	var T int
	fmt.Scan(&T)
	for i := 0; i < T; i++ {
		var n, k int
		fmt.Scan(&n, &k)
		arr := make([]int, n)
		for j := 0; j < n; j++ {
			fmt.Scan(&arr[j])
		}
		S, cnt := 0, 0
		for p := 0; p < n; p++ {
			if arr[p] >= k {
				S += arr[p]
			} else if arr[p] == 0 && S >= 1 {
				S -= 1
				cnt += 1
			}
		}
        fmt.Println(cnt)
	}
}

发表于 2025-06-29 15:40:13 回复(0)
拒绝无效加班的柯基很想被叫靓仔头像 拒绝无效加班的柯基很想被叫靓仔
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int T = in.nextInt();
            int n,k;
            for(int i = 0;i < T;i++){
                n = in.nextInt();
                k = in.nextInt();
                int[] arr = new int[n];
                int s = 0,cnt = 0;
                for(int j = 0;j < n;j++)
                {
                    arr[j] = in.nextInt();
                    if(arr[j] >= k){s += arr[j];}
                    if(arr[j] == 0 && s >= 1){s -= 1;cnt += 1;}
                }
                System.out.println(cnt);
            }
        }
    }
}
发表于 2025-06-27 16:12:44 回复(0)
Python3
牛客83749222号头像 牛客83749222号
T=int(input())
for __ in range(T):
    n,k=list(map(int,input().split()))
    a=list(map(int,input().split()))
    s=0
    cnt=0
    for i in range(n):
        if a[i]>=k:
            s+=a[i]
        if a[i]==0 and s>=1:
            s-=1
            cnt+=1
    print(cnt)
发表于 2025-06-24 11:27:22 回复(0)
提交观点

问题信息

难度：
13条回答 82浏览

热门推荐

相关试题

数组计数维护

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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