首页 > 试题广场 >

数组计数维护

[编程题]数组计数维护

热度指数：1757 时间限制：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$ 的值。

输入描述:

第一行输入一个整数 ，表示测试用例组数。
每组测试用例格式如下：
第一行输入两个整数 ；
第二行输入  个整数 .

输出描述:

对于每组测试用例，输出一行一个整数，表示  的值。

示例1

输入

输出

1
0
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)