首页 > 试题广场 >

数组计数维护

[编程题]数组计数维护
  • 热度指数：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。
算法知识视频讲解
添加回答
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)
提交观点

问题信息

难度：
1条回答 414浏览

热门推荐

相关试题

数组计数维护

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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