罪犯转移用滑动窗口做，一次AC

迷南。 2022-09-26 02:57 18阅读 0赞

罪犯转移

*  热度指数：2731时间限制：1秒空间限制：32768K
 *  本题知识点： [动态规划][Link 1]
 *  [ 算法知识视频讲解][Link 2]

## 题目描述 ##

C市现在要转移一批罪犯到D市，C市有n名罪犯，按照入狱时间有顺序，另外每个罪犯有一个罪行值，值越大罪越重。现在为了方便管理，市长决定转移入狱时间连续的c名犯人，同时要求转移犯人的罪行值之和不超过t，问有多少种选择的方式？

##### 输入描述: #####

第一行数据三个整数:n，t，c(1≤n≤2e5,0≤t≤1e9,1≤c≤n)，第二行按入狱时间给出每个犯人的罪行值ai(0≤ai≤1e9)

##### 输出描述: #####

一行输出答案。

##### 输入例子: #####

3 100 2
    1 2 3

##### 输出例子: #####

思路：先算前c个的和，然后依次往后面移动，每次移动一个位置（数组中的一个下标），重新计算和。

每次计算完和后，与t比较是否超过限制。如果没超限制，种类数加1.

最后输出种类数。

import java.util.*;
    public class Main{
        public static void main(String[] args){
            Scanner scan = new Scanner(System.in);
            int n,t,c;
            while(scan.hasNext()){
                n=scan.nextInt();
            	t=scan.nextInt();
            	c=scan.nextInt();
                int cnt=0;
                int[] a = new int[n];
                for(int i=0;i<n;i++){
                    a[i]=scan.nextInt();
                }
                int sum =0;
                for(int i=0;i<c;i++){
                    sum+=a[i];
                }
                
                if(sum<=t)cnt++; 
                for(int i=0;i<n-c;i++){
                    if(sum<=t){
                        cnt++;
                    }
                    sum-=a[i];
                    sum+=a[i+c];
                }
                System.out.println(cnt);
            }
            
        }
    }

[Link 1]: http://www.nowcoder.com/questionCenter?questionTypes=000100&mutiTagIds=593
[Link 2]: http://www.nowcoder.com/courses/1