罪犯转移

题目描述

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

 

多组数据

 

1 //先计算前c个数的累加值sum，之后将指针i指向数组下标c处，指针每前移一位， 2 //sum-=a[i-c]; sum+=a[i];使效率变为O(n) 3 #include 
     
       4 using namespace std; 5 int weight[200005]; 6    7 int main(){ 8     int n, t, c; 9     while(cin >> n >> t >> c){10         int i, sum = 0, cnt = 0;11         for(i = 0; i < n; ++i)12             cin >> weight[i];13         if(c > n) continue;14         for(i = 0; i < c; ++i)15             sum += weight[i];16         if(sum <= t) ++cnt;17         for(i = c; i < n; ++i){18             sum -= weight[i-c];19             sum += weight[i];20             if(sum <= t) ++cnt;21         }22         cout << cnt << endl;23     }24     return 0;25 }
     

 

 

运行超时：

1 #include 
     
       2 using namespace std; 3 int n,t,c; 4 int a[200005]; 5 int ans=0; 6 int main(){ 7     while(cin>>n>>t>>c){ 8         for(int i=1;i<=n;i++){ 9                cin>>a[i];10         }11         for(int i=1;i<=n-c+1;i++){12             int sum=0;13             for(int j=0;j