首页 > 代码库 > [百度]罪犯转移

[百度]罪犯转移

时间限制:1秒 空间限制:32768K 热度指数:34020
本题知识点: 动态规划

题目描述

C市现在要转移一批罪犯到D市,C市有n名罪犯,按照入狱时间有顺序,另外每个罪犯有一个罪行值,值越大罪越重。现在为了方便管理,市长决定转移入狱时间连续的c名犯人,同时要求转移犯人的罪行值之和不超过t,问有多少种选择的方式?

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


输出描述:
一行输出答案。

输入例子:
3 100 2
1 2 3

输出例子:
2
思路:
利用动态规划的思想解决,首先计算前c个罪行值之和,然后每移动一个单位,减去第一个元素,再加上新增加的元素。
 1 #include<iostream>  
 2 #include<vector>  
 3   
 4 using namespace std;  
 5 
 6 int main()
 7     {
 8        int n,t,c,a;
 9        while(cin>>n>>t>>c)
10            {
11               vector<int> cri;//用来存罪犯的罪行值
12               for(int i=0;i<n;++i)
13                   {
14                      cin>>a;
15                      cri.push_back(a);
16                   
17               }
18            int count=0;
19            int sum=0;
20            
21            for(int i=0;i<c;++i)
22                {
23                  sum+=cri[i];
24                
25            }
26            if(sum<=t)
27                ++count;
28            for(int i=1;i<=cri.size()-c;++i)
29                {
30                   sum-=cri[i-1];
31                   sum+=cri[i+c-1];
32                   if(sum<=t)
33                       ++count;
34                
35            }
36            cout<<count<<endl;
37        }
38     return 0;
39 }

 


[百度]罪犯转移