笔试刷题-百度2018-06-22

题目描述：

/**
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

输出例子1:
2
*/

思路如下：

采用双向队列维护一个c大小滑动窗口即可
并更新即可计数即可

代码如下：

#include<stdio.h>
#include<iostream>
#include<deque>

#define MAX_N 200005

using namespace std;

int arr[MAX_N];

int main()
{
    int N, T, C;

    while(scanf("%d%d%d", &N, &T, &C)==3)
    {
        deque<int> que;
        for(int i=0; i<N; i++)
            scanf("%d", arr+i);
        int acc=0, res=0;
        //C>0 init que.size()==0
        for(int i=0; i<N; i++)
        {
            if(que.size()<C)
            {
                que.push_back(arr[i]);
                acc+=arr[i];
            }
            else if(que.size()==C)
            {
                int head=que.front();
                que.pop_front();
                acc-=head;
                que.push_back(arr[i]);
                acc+=arr[i];
            }
            if(acc<=T && que.size()==C)
            {
                res++;
            }
            else if(acc>T)
            {
                while(!que.empty() && acc>T)
                {
                    int head=que.front();
                    que.pop_front();
                    acc-=head;
                }
            }
        }
        printf("%d\n", res);
    }
    return 0;
}