首页 > 试题广场 >

数组计数维护

[编程题]数组计数维护
  • 热度指数:1625 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定正整数 n 和阈值 k 以及长度为 n 的整数序列 \{a_1,a_2,\dots,a_n\}
\hspace{15pt}你需要动态地维护两个正整数变量 Scnt,初始时,S=cnt=0
\hspace{15pt}按照从 1n 的顺序,对每个下标 i 执行:
\hspace{23pt}\bullet\,a_i \ge k,则 S \leftarrow S + a_i
\hspace{23pt}\bullet\,a_i = 0S \ge 1,则 S \leftarrow S - 1cnt \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],第 12 \ge 2S=2;第 2 项为 0S\ge1,赠出 1 枚,cnt=1;第 3 项无操作;因此 cnt=1
\hspace{15pt}对于第三组数据:
\hspace{23pt}\bullet\,n=5,k=3,a=[3,0,0,4,0],第 13\ge3S=3;第 2,3 项各赠出 1 枚,cnt=2,S=1;第 44\ge3S=5;第 5 项再赠出 1 枚,cnt=3;因此 cnt=3
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)