题解 | 罪犯转移

罪犯转移

https://www.nowcoder.com/practice/b7b1ad820f0a493aa128ed6c9e0af448

解题思路

这是一个典型的滑动窗口问题：

需要找出长度为 $c$ 的连续子数组
子数组的和不能超过 $t$
统计满足条件的子数组个数

关键点

使用滑动窗口维护连续 $c$ 个元素的和
注意处理多组测试数据
数据范围较大，注意使用long long类型

代码

cpp
java
python

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    long long countValidTransfers(int n, long long t, int c, vector<int>& crimes) {
        long long count = 0;
        long long windowSum = 0;
        
        // 计算第一个窗口的和
        for (int i = 0; i < c; i++) {
            windowSum += crimes[i];
        }
        
        // 如果第一个窗口满足条件，计数加1
        if (windowSum <= t) {
            count++;
        }
        
        // 滑动窗口
        for (int i = c; i < n; i++) {
            // 更新窗口和：减去窗口最左边的值，加上新的值
            windowSum = windowSum - crimes[i-c] + crimes[i];
            
            // 检查当前窗口是否满足条件
            if (windowSum <= t) {
                count++;
            }
        }
        
        return count;
    }
};

int main() {
    int n, c;
    long long t;
    
    // 处理多组测试数据
    while (cin >> n >> t >> c) {
        vector<int> crimes(n);
        for (int i = 0; i < n; i++) {
            cin >> crimes[i];
        }
        
        Solution solution;
        cout << solution.countValidTransfers(n, t, c, crimes) << endl;
    }
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public long countValidTransfers(int n, long t, int c, int[] crimes) {
            long count = 0;
            long windowSum = 0;
            
            // 计算第一个窗口的和
            for (int i = 0; i < c; i++) {
                windowSum += crimes[i];
            }
            
            // 如果第一个窗口满足条件，计数加1
            if (windowSum <= t) {
                count++;
            }
            
            // 滑动窗口
            for (int i = c; i < n; i++) {
                // 更新窗口和
                windowSum = windowSum - crimes[i-c] + crimes[i];
                
                // 检查当前窗口是否满足条件
                if (windowSum <= t) {
                    count++;
                }
            }
            
            return count;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 处理多组测试数据
        while (sc.hasNext()) {
            int n = sc.nextInt();
            long t = sc.nextLong();
            int c = sc.nextInt();
            
            int[] crimes = new int[n];
            for (int i = 0; i < n; i++) {
                crimes[i] = sc.nextInt();
            }
            
            Solution solution = new Solution();
            System.out.println(solution.countValidTransfers(n, t, c, crimes));
        }
        
        sc.close();
    }
}

class Solution:
    def count_valid_transfers(self, n: int, t: int, c: int, crimes: list) -> int:
        count = 0
        window_sum = 0
        
        # 计算第一个窗口的和
        for i in range(c):
            window_sum += crimes[i]
        
        # 如果第一个窗口满足条件，计数加1
        if window_sum <= t:
            count += 1
        
        # 滑动窗口
        for i in range(c, n):
            # 更新窗口和
            window_sum = window_sum - crimes[i-c] + crimes[i]
            
            # 检查当前窗口是否满足条件
            if window_sum <= t:
                count += 1
        
        return count

def main():
    # 处理多组测试数据
    while True:
        try:
            n, t, c = map(int, input().split())
            crimes = list(map(int, input().split()))
            
            solution = Solution()
            print(solution.count_valid_transfers(n, t, c, crimes))
        except EOFError:
            break

if __name__ == "__main__":
    main()