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