首页 > 代码库 > 百度罪犯转移

百度罪犯转移

题目描述

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
输出例子:
2
代码:

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

 收获:(1)一开始用两个for循环超时;回来用滑动窗口的原理就不用两个for循环;

         for(int i=c;i<n;i++){
          zx=zx+zui[i]-zui[i-c];

(2)注意,大多数的题都要输入多组数据;

  while(sc.hasNext()),否则通不过。

 


百度罪犯转移