题解 | #数组计数维护#

题目链接

数组计数维护

题目描述

给定一个长度为 n 的整数序列 a 和一个阈值 k。你需要动态维护两个变量 S 和 cnt，它们的初始值都为 0。然后，按照从 1 到 n 的顺序遍历序列 a，对每个元素 a[i] 执行以下操作：

如果 a[i] >= k，则 S 的值增加 a[i]。
若不满足上一条，且 a[i] == 0 并且 S >= 1，则 S 的值减 1，同时 cnt 的值加 1。
否则，不进行任何操作。

你需要处理 T 组这样的测试用例，并对每一组输出最终 cnt 的值。

输入描述:

第一行是一个整数 T，表示测试用例组数。
对于每组测试用例：
- 第一行是两个整数 n 和 k。
- 第二行是 n 个整数，代表序列 a。

输出描述:

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

解题思路

本题是一个典型的模拟题。我们只需要完全按照题目描述的逻辑来编写代码即可。问题的核心是正确地实现对变量 S 和 cnt 的更新规则。

算法步骤（针对单个测试用例）：

初始化: 读取 n 和 k。定义两个变量 S = 0 和 cnt = 0。
循环处理: 为了让代码结构更清晰，推荐的做法是先将所有 n 个数字读入一个数组，然后再遍历这个数组进行处理。
应用规则: 遍历存储好的数组，对于每一个数字 a_i：
- 使用 if-else if 结构来确保规则的互斥性。
- if (a_i >= k): 如果当前数字大于等于阈值 k，则执行 S += a_i。
- else if (a_i == 0 && S > 0): 如果第一个条件不成立，我们接着判断当前数字是否等于0并且S是否大于0。如果条件都满足，则执行 S-- 和 cnt++。
- else: 如果以上两个条件都不成立，则不执行任何操作。
输出结果: 当循环 n 次结束后，cnt 变量中存储的就是最终的答案。输出 cnt。

主程序结构: 最外层是一个循环，用于处理 T 组测试用例。在循环内部调用一个 solve() 函数来处理单个测试用例的逻辑，这样可以让代码结构更清晰。

代码

c++
java
python

#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];
    }

    long long S = 0;
    int cnt = 0;
    
    // 再遍历数组进行处理
    for (int a_i : a) {
        if (a_i >= k) {
            S += a_i;
        } else if (a_i == 0 && S > 0) {
            S--;
            cnt++;
        }
    }
    
    cout << cnt << endl;
}

int main() {
    // 处理多组输入
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    // 处理单个测试用例的函数
    public static void solve(Scanner sc) {
        int n = sc.nextInt();
        int k = sc.nextInt();
        
        int[] a = new int[n];
        // 先将所有数字读入数组
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        long S = 0;
        int cnt = 0;
        
        // 再遍历数组进行处理
        for (int a_i : a) {
            if (a_i >= k) {
                S += a_i;
            } else if (a_i == 0 && S > 0) {
                S--;
                cnt++;
            }
        }
        
        System.out.println(cnt);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            solve(sc);
        }
    }
}

# 处理单个测试用例的函数
def solve():
    n, k = map(int, input().split())
    # 读取序列a
    a = list(map(int, input().split()))
    
    S = 0
    cnt = 0
    
    for a_i in a:
        if a_i >= k:
            S += a_i
        elif a_i == 0 and S > 0:
            S -= 1
            cnt += 1
            
    print(cnt)

# 处理多组测试用例的主循环
T = int(input())
for _ in range(T):
    solve()

算法及复杂度

算法：直接模拟。
时间复杂度：对于每组测试用例，我们需要遍历一次包含 n 个元素的序列。因此，处理单组数据的复杂度是 $\mathcal{O}(n)$ 。
空间复杂度：我们将序列存储在一个数组或列表中，因此空间复杂度为 $\mathcal{O}(n)$ 。