列表

详情


BD1. 罪犯转移

描述

C市现在要转移一批罪犯到D市,C市有n名罪犯,按照入狱时间有顺序,另外每个罪犯有一个罪行值,值越大罪越重。现在为了方便管理,市长决定转移入狱时间连续的c名犯人,同时要求转移犯人的罪行值之和不超过t,问有多少种选择的方式(一组测试用例可能包含多组数据,请注意处理)?

输入描述

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

输出描述

一行输出答案。

示例1

输入:

3 100 2
1 2 3

输出:

2

原站题解

C 解法, 执行用时: 12ms, 内存消耗: 640KB, 提交时间: 2021-09-08

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int n,t,c,a;
    while(scanf("%d %d %d",&n, &t, &c)!=EOF)
    {
    
         int count = 0;
        int arr[n];
        arr[0] = 0;   
		for(int i = 1; i <= n; i++){
			scanf("%d", &a);
			arr[i] =arr[i-1]+a ;
		}

		for(int i = n ;i >=c ;i--)
		{
			if(arr[i] - arr[i-c] <=t)
			    count = count +1;
		}
		 printf("%d\n", count);
	}
    return 0;
}

C++ 解法, 执行用时: 12ms, 内存消耗: 700KB, 提交时间: 2021-09-14

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int n,t,c,a;
    while(scanf("%d %d %d",&n, &t, &c)!=EOF)
    {
    
         int count = 0;
        int arr[n];
        arr[0] = 0;   
		for(int i = 1; i <= n; i++){
			scanf("%d", &a);
			arr[i] =arr[i-1]+a ;
		}

		for(int i = n ;i >=c ;i--)
		{
			if(arr[i] - arr[i-c] <=t)
			    count = count +1;
		}
		 printf("%d\n", count);
	}
    return 0;
}

C++14 解法, 执行用时: 13ms, 内存消耗: 736KB, 提交时间: 2020-09-04

#include<stdio.h>
  
int main(){
    int n ,t, c;
    int a, s[200005], count=0;
    s[0]=0;
    while(scanf("%d %d %d",&n, &t, &c)!=EOF){
        count = 0;
        s[0] = 0;
    for(int i = 1; i <= n; i++){
        scanf("%d", &a);
        s[i] = s[i-1]+a;
    }
    for(int i = n; i >= c; i--){
        if(s[i] - s[i-c] <= t)
            count++;
    }
    printf("%d\n", count);
}
    return 0;
}

C++ 解法, 执行用时: 13ms, 内存消耗: 772KB, 提交时间: 2021-09-14

#include<iostream>
#include<cstdio>
#define ll long long 
#define maxn 200007
using namespace std;

int num[maxn];

int main() {
    int n,t,c;
    while(~scanf("%d %d %d", &n,&t,&c)) {
        num[0]=0;
        for(int i=1;i<=n;++i) {
            scanf("%d", &num[i]);
            num[i] += num[i-1];
        }
        int cnt=0;
        for(int i=0;i+c<=n;++i){
            if(num[i+c]-num[i]<=t) {
                ++cnt;
            }
        }
            
        printf("%d\n",cnt);
    }
}

C 解法, 执行用时: 13ms, 内存消耗: 956KB, 提交时间: 2020-09-08

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int i,j,n,t,c,a;
    int count = 0;

    int arr[200005];
    while(scanf("%d %d %d",&n, &t, &c)!=EOF){
    
        count = 0;
        arr[0] = 0;   
		for(i = 1; i <= n; i++){
			scanf("%d", &a);
			arr[i] =arr[i-1]+a ;
		}

		for(i = n ;i >=c ;i--)
		{
			if(arr[i] - arr[i-c] <=t)
			    count = count +1;
		}
		 printf("%d\n", count);
	}
    return 0;
}

上一题