算法-每天一道题（8）-罪犯转移

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

C++

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    int n,t,c;
    int temp;
    int count = 0;
    int value = 0;
    while(cin >> n >> t >> c)
    {
        vector<int> A;
        for (int i=0; i<n; i++)
        {
            cin >> temp;
            A.push_back(temp);
        }
        /*
        // 另一种放入向量A的方式
        vector<int> A(n);
        for (int i=0; i<n; i++)
            cin >> A[i];
        */

        // 算出从开头到选择人数的长度的值
        for (int i=0; i<=c-1; i++)
            value = value+A[i];
        
        if (value<t)
            count++;
            
        // 看作定长游标，一格格向右移动，这样的时间复杂度为n
        for (int i=0; i<=n-c-1; i++)
        {
            value = value - A[i] + A[i+c];
            if (value>t)
                continue;
            else
                count++;
        }
        // 有多次循环，所以需要将值输出并清空
        cout<<count<<endl;
        value = 0;
        count = 0;
    }
    
    return 0;
}

/*
解题思路：

其实这道题主要是输入和输出的部分比较坑。
由于是连续的c名犯人，所以只需要保持该长度移动就可以了，
算出它的值，与t进行比较。
*/

C++时间复杂度过大的算法

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n,t,c;
    int temp;
    int count = 0;
    int value = 0;
    while(cin>>n>>t>>c)
    {
        if (c>n || c<0)
            return -1;
        vector<int> A;
        for (int i=0; i<n; i++)
        {
            cin >> temp;
            A.push_back(temp);
        }
        for (int i=0; i<=n-c; i++)
        {
            for (int j=i; j<=i+c-1; j++)
            	value = value+A[j];
            if (value>t)
            {
                value = 0;
            	continue;
            }
            else
            	count++;
            value = 0;
        }
        cout<<count<<endl;
        count = 0;
    }
    
    return 0;
}
/*和上一种类似，只是重复计算的次数比较多，导致时间过长*/

Python版本时间过长[且只实现了一个case]，仅作参考

import sys

if __name__ == "__main__":
    answer = []
    for item in sys.stdin:
        answer.append(item)
    line_1 = answer[0].strip("\n").split(" ")
    line_2 = answer[1].strip("\n").split(" ")
    n = int(line_1[0])
    t = int(line_1[1])
    c = int(line_1[2])
    value = 0
    count = 0
    for i in xrange(0, n-c+1):
        for j in xrange(i, i+c):
            value = value+int(line_2[i])
        if value > t:
            value = 0
            continue
        else:
            count = count + 1
            value = 0
    print count