首页 > 试题广场 >

数组计数维护

[编程题]数组计数维护
  • 热度指数：13324 时间限制：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
反转秋刀鱼头像 反转秋刀鱼 
#include <stdio.h>
int main()
{
    int T=0;
    int n=0,k=0;
    int cnt=0,S=0;
    scanf("%d",&T);
    int a[1000000];
    for(int t=0;t<T;t++)
    {
        cnt=0,S=0;
        scanf("%d %d",&n,&k);
        for(int j=0;j<n;j++)
        {
            scanf("%d",&a[j]);
            if(a[j]>=k)
            {
                S=S+a[j];
            }
            else if(a[j]==0&&S>=1)
            {
                S=S-1;
                cnt=cnt+1;
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}
不难，直接把题目要求一步步翻译下来就行，需要注意的就是记住循环的初始化数据，那会因为忘了每次初始化cnt    S，导致没过用例
以上，谢谢\(￣︶￣*\))
发表于 2025-12-05 19:36:05 回复(0)
Python3
意若久时天然呆头像 意若久时天然呆 
T = int(input())
for _ 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]
        if a[i] == 0 and s >= 1:
            s -= 1
            cnt += 1
    print(cnt)

发表于 2025-11-04 11:05:43 回复(0)
C++
来吾告汝头像 来吾告汝 
#include <iostream>
using namespace std;
#include <vector>

int main() {
    int T;
    cin >> T;
    for(int i = 0; i < T; ++i)
    {
        int n,k;
        cin >> n >> k;
        int s = 0, cnt = 0;
        vector<int> v(n,0);
        for(auto& num : v)
        {
            cin >> num;
            if(num >= k) s += num;
            if(num == 0 && s >= 1) {s -= 1; cnt += 1;}
        }
        cout << cnt << endl;
    }
}

发表于 2025-12-13 02:59:15 回复(0)
C
Neoxx头像 Neoxx 
#include <stdio.h>

int main() {
    int T,n,k,a[100];
    scanf("%d",&T);
    for(int i=0;i<T;i++){
        int s=0,cnt=0;
        scanf("%d%d",&n,&k);
        for(int j=0;j<n;j++)
            scanf("%d",&a[j]);
        for(int j=0;j<n;j++){
            if(a[j]>=k)
                s+=a[j];
            else if(a[j]==0&&s>=1){
                s--;
                cnt++;
            }        
        }
        printf("%d\n",cnt);    
    }
    return 0;
}

发表于 2025-11-17 21:42:55 回复(0)
Python3
农骆驼头像 农骆驼 
t = int(input())
for _ in range(t):
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    s = 0
    cnt = 0
    for i in a:
        if i>=k:
            s += i
        if i == 0 and s>=1:
            s -= 1
            cnt += 1
    print(cnt)

发表于 2025-11-11 19:12:36 回复(0)
C++
聪敏的豹子渴望wlb头像 聪敏的豹子渴望wlb
#include <iostream>
using namespace std;

int main() {
    int t;
    cin>>t;//输入测试组数
    while(t--){//执行t次，执行三组
        int n,k;
        cin>>n>>k;//读入组内有n个数，及比较数字k
        int cnt=0;int s=0;
        for(int i=0;i<n;i++){
            int a;cin>>a;//读入组内数字
        if(a>=k){s+=a;//组内数字逐一与k比较大小，若a>k，如a=3>k=2,则s+3
            
        }else if(a==0&&s>=1){//另一种情况：若是a=0，且此时s>=1,则s-1；并cnt+1
            s-=1;
            cnt+=1;
        }//不满足以上两种情况就什么都不做
        }cout<<cnt<<endl;
    }return 0;
}
// 64 位输出请用 printf("%lld")
发表于 2025-09-28 13:49:54 回复(0)
C
L1LL头像 L1LL 
#include <stdio.h>

int main() {
    int T;
    if (scanf("%d", &T) != 1 || T < 1 || T > 10000) {
        return 1;
    }
    for (int i = 0; i < T; i += 1) {
        int n, k;
        if (scanf("%d %d", &n, &k) != 2 || n < 1 || n > 50 || k < 1 || k > 100) {
            return 1;
        }
        int S = 0, cnt = 0;
        for (int j = 0; j < n; j += 1) {
            int a;
            if (scanf("%d", &a) != 1 || a < 0 || a>100) {
                return 1;
            }
            if (a >= k) {
                S += a;
            }
            if (a == 0 && S >= 1) {
                S -= 1;
                cnt += 1;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

发表于 2026-01-08 00:28:49 回复(0)
牛客459616581号头像 牛客459616581号
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int i = 0 ; i < T; i++ ){
            int n = sc.nextInt();
            int k = sc.nextInt();
            int arr[] = new int[n];
            int S = 0;
            int cnt = 0;
            for(int j = 0;j < arr.length; j++){
                int num = sc.nextInt();
                arr[j] = num;
            }
            for(int j = 0;j < arr.length; j++){
                if(arr[j] >= k){
                    S += arr[j];
                }else if (arr[j] == 0 &&  S >= 1){
                    S -= 1;
                    cnt += 1;
                }
            }
            System.out.println(cnt);
        }
    }
}
发表于 2026-01-07 16:20:13 回复(0)
C++
24届攒钱辞职的小牛马头像 24届攒钱辞职的小牛马
方法1:未使用数组，全部用例耗时为98ms，占用内存为532kb 
#include <cassert>
#include <iostream>

int main() {
    int T;
    std::cin >> T;
    assert(1 <= T && T <= 10000);

    for (int t = 0; t < T; ++t) {
        int n, k;
        std::cin >> n >> k;
        assert(1 <= n && n <= 50);
        assert(1 <= k && k <= 100);
        int s = 0, cnt = 0;

        for (int i = 0; i < n; ++i) {
            int x;
            std::cin >> x;
            assert(0 <= x && x <= 100);

            if (x >= k) {
                s += x;
            } else if (x == 0 && s >= 1) {
                s -= 1;
                cnt += 1;
            }
        }
        std::cout << cnt << "\n";
    }

    return 0;
}
方法2 使用数组 
#include <cassert>
#include <iostream>
#include <vector>

int main() {
    int T;
    std::cin >> T;
    assert(1 <= T && T <= 10000);

    for (int t = 0; t < T; ++t) {
        int n, k;
        std::cin >> n >> k;
        assert(1 <= n && n <= 50);
        assert(1 <= k && k <= 100);
        int s = 0, cnt = 0;

        std::vector<int> a(n, 0);

        for (auto &x : a) {
            std::cin >> x;
            if (x >= k) {
                s += x;
            } else if (x == 0 && s >= 1) {
                s -= 1;
                cnt += 1;
            }
        }
        std::cout << cnt << std::endl;
    }

    return 0;
}



发表于 2026-01-05 18:02:33 回复(0)
在刷题的老f很苦头像 在刷题的老f很苦
#include <stdio.h>
#include<stdlib.h>
int main(){
   int T;scanf("%d",&T);
   int n,k;
   int S=0,cnt=0;
   for(int i=0;i<T;i++)
   {  
       scanf("%d %d",&n,&k);
       int *arr=(int*)calloc(n,sizeof(int));
       if(arr==NULL)
       {
          printf("失败");
          return 1;
       }
       for(int i=0;i<n;i++)
       {
           scanf("%d",&arr[i]);
       }
       for(int j=0;j<n;j++)
       {
            if(arr[j]>=k)
                S+=arr[j];
            if(arr[j]==0&&S>=1)
            {
                S-=1;
                cnt+=1;
            }      
       }
       printf("%d\n",cnt);
       free(arr);
       arr=NULL;
       S=0;
       cnt=0;
   }  
}
发表于 2026-01-02 14:32:22 回复(0)
Python3
爱健身的牛油果很愤怒头像 爱健身的牛油果很愤怒
T = int(input())

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

    for i in A:
        if i>=k:
            S=S+i
        if i==0 and S>=1:
            S=S-1
            cnt=cnt+1
    print(cnt)

发表于 2025-12-22 21:19:53 回复(0)
萱99头像 萱99 
#include <stdio.h>

int main() {
int S=0,cnt=0;
int T;
int n,k;
int a[10000];
scanf("%d",&T);
for (int i=0; i<T; i++) {
    S=0;
    cnt=0;
    
scanf("%d %d",&n,&k);


for(int j=0;j<n;j++){
    scanf("%d",&a[j]);
if (a[j]>=k) {
S=S+a[j];
}else if (a[j]==0&&S>=1) {
S=S-1;
cnt=cnt+1;
}
}
printf("%d\n",cnt);
}    
return 0;
}

发表于 2025-12-21 17:35:11 回复(0)
有担当的做题家在努力存钱头像 有担当的做题家在努力存钱
n = int(input())
result = []
for _ in range(n):
    a , b =map(int,input().split())
    c = map(int,input().split())
    d = list(c)
    s = 0
    cnt = 0
    for x in d:
        if x >= b:
            s += x
        elif (x == 0)&(s>=1):
            cnt +=1
    result.append(str(cnt))
print(print(' '.join(result)))
发表于 2025-12-20 15:55:00 回复(0)
北辰007头像 北辰007
#include <stdio.h>
#include <stdlib.h>

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

发表于 2025-11-18 21:34:27 回复(0)
Comeand头像 Comeand
#include <stdio.h>

int main() {
    int T,n,k,S,cnt;
    int arr[100];
    scanf("%d",&T);
    for(int i=0;i<T;i++){
        scanf("%d %d",&n,&k);
        S=cnt=0;
        for(int j=0;j<n;j++){
            scanf("%d",&arr[j]);
            if(arr[j]>=k){
                S=S+arr[j];
            }
            else if(arr[j]==0&&S>=1){
                S-=1;
                cnt+=1;
            }
        }
        printf("%d\n",cnt);
       
    }
   
    return 0;
}
发表于 2025-11-09 14:47:35 回复(0)
Java
年岁不可更头像 年岁不可更
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        //定义键盘录入
        Scanner sc=new Scanner(System.in);
        //定义一个数组
        int[] arr=new int[50];
        //输入整数T，表示测试用例组数
        int T=sc.nextInt();
        for(int i=0;i<T;i++){
            //定义两个变量S，cnt
            int S=0,cnt=0;
            //录入整数n，k分别表示需要测试整数个数和阈值
            int n=sc.nextInt();
            int k=sc.nextInt();
            //录入1组测试数据
            for(int j=0;j<n;j++){
                arr[j]=sc.nextInt();
            }
            //计算S和cnt的值
            for(int x=0;x<n;x++){
                if(arr[x]>=k){
                S+=arr[x];
                }
                if(arr[x]==0&&S>=1){
                    S-=1;
                    cnt+=1;
                }
            }
            //打印cnt的值
            System.out.println(cnt);
        }
   
    }      
}
发表于 2025-11-02 19:59:26 回复(0)
牛客134990458号头像 牛客134990458号 
#include <stdio.h>

int main() {
    //定义组数，序列长度，阈值
    int g, n, k;
    //定义s，cnt，缓存变量接收数字序列
    int s, cnt, tmp;

    scanf("%d", &g);

    int i = 0, j;
    while (i++ < g) { 
        //初始化s，cnt，j
        s = 0;
        cnt = 0;
        j = 0;

        scanf("%d %d", &n, &k);

        while (j++ < n) {
            scanf("%d", &tmp);
            if(tmp >= k) s += tmp;
            else if( !tmp && s >= 1) {s--; cnt++;}
        }
        //直接输出cnt
        printf("%d\n", cnt);
    }
    return 0;
}

发表于 2025-11-01 16:41:53 回复(0)
牛客942052331号头像 牛客942052331号 
import sys

def fn(k,lst):
    s=cnt=0
    for i in lst:
        if i>=k:
            s+=i
        elif i==0 and s>=1:
            s-=1
            cnt+=1
        else:
            continue
    return cnt


datas = [line.strip() for line in sys.stdin][1:]

for nums,data in zip(datas[::2], datas[1::2]):
    n,k = list(map(int,nums.split()))
    data = list(map(int,data.split()))
    cnt = fn(k,data)
    print(cnt)

发表于 2025-10-28 23:38:31 回复(0)
C++
吃柠檬的袋鼠头像 吃柠檬的袋鼠
#include <iostream>
#include<vector>
using namespace std;

int main() {
    int T;                                      // 测试用例组数
    cin>>T;

    while(T--){
        int n,k;
        cin>>n>>k;

        vector<int> a(n);                       // 数组a[n]
        for(int i=0;i<n;++i){                   // 循环读取所有数字，存到数组a[n]
            cin>>a[i];
        }

        long long S =0;                         //初始时，S=cnt=0
        int cnt = 0;

        for(auto a_i :a){                       // 遍历数组a[n]
            if(a_i>=k){                         //a[i]>=k的情况
                S = S + a_i;
            }
            else if(a_i==0 && S>=1){            // a[i]=0且S>=1的情况
                S = S-1;
                cnt = cnt+1;
            }
            else{                               // 什么也不做
                ;
            }
        }
        cout<<cnt<<endl;
    }
}
// 64 位输出请用 printf("%lld")
发表于 2025-10-19 16:20:17 回复(0)
提交观点

问题信息

难度：
45条回答 411浏览

热门推荐

相关试题

数组计数维护

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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