首页 > 试题广场 >

罪犯转移

[编程题]罪犯转移
  • 热度指数：40756 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
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
算法知识视频讲解
添加回答
qibofang头像 qibofang 
//先计算前c个数的累加值sum，之后将指针i指向数组下标c处，指针每前移一位，
//sum-=a[i-c]; sum+=a[i];使效率变为O(n)
#include <iostream>
using namespace std;
int weight[200005];
 
int main(){
    int n, t, c;
    while(cin >> n >> t >> c){
        int i, sum = 0, cnt = 0;
        for(i = 0; i < n; ++i)
            cin >> weight[i];
        if(c > n) continue;
        for(i = 0; i < c; ++i)
            sum += weight[i];
        if(sum <= t) ++cnt;
        for(i = c; i < n; ++i){
            sum -= weight[i-c];
            sum += weight[i];
            if(sum <= t) ++cnt;
        }
        cout << cnt << endl;
    }
    return 0;
}

发表于 2016-08-23 12:41:44 回复(0)
darren_wang头像 darren_wang 
#include<iostream>
#include<vector>
using namespace std;
int main(void){
    int n, t, c; //犯人个数，总犯罪值，连续犯人数
    while(cin >> n >> t >> c){ //这里是最恶心的，需要自己处理“多个输入测试用例”
        vector<int> val(n);
        int sum=0, count=0;
        for(int i=0; i<n; i++){
            cin >> val[i];
            if(i<c) sum += val[i];
        }
        if (sum<=t) count++;
        for(int i=0; i+c<n; i++){
            sum += val[i+c]-val[i];
            if(sum<=t) count++;
        }
        cout << count <<endl;
    }
    return 0;
}

发表于 2015-09-27 18:39:47 回复(12)
C/C++
卷积神经网络哦头像 卷积神经网络哦

这种类似的可以扫描一趟的题目还是挺多的， 常用的技巧是一左一右两个“指针”。可以在O(n)的时间内解决(最**的方法是O(n^2)的暴力)
保持长度为c，一趟扫下来每次判断一下即可 

#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 2e5 + 1;
int arr[maxn];

int main(){
    int n, t, c;
    while(scanf("%d%d%d", &n, &t, &c) == 3){
        memset(arr, 0, sizeof(arr));
        for(int i=0;i<n;i++) scanf("%d", &arr[i]);
        int sum = 0, l = 0, r = c - 1, cnt = 0;
        for(int i=l; i<=r; i++) sum += arr[i];
        while(r < n){
            if(sum <= t) cnt += 1;
            r++; l++;
            sum = sum + arr[r] - arr[l-1];
        }
        cout<<cnt<<endl;
    }
    return 0;
}
编辑于 2018-08-27 11:24:02 回复(0)
lensh头像 lensh 
#include<iostream>  
#include<vector>
using namespace std;
int main()  
{  
    int n,t,c; //犯人个数，总犯罪值，连续犯人数
    while(cin >> n >> t >> c){
        cin>>n>>t>>c;
   	    vector<int> a(n);
   	    int sum=0,count=0;
        for(int i=0;i<n;i++){
    	    cin>>a[i];
    	    if(i<c) sum+=a[i];
        }
        if(sum<=t) count++;
        for(int i=0;i<n-c;i++){
    	    sum+=a[i+c]-a[i];
	    if(sum<=t) count++;
        }
        cout<<count<<endl;
    }
    return 0;  
}
利用滑动窗口的思想，假设是这样的序列：012 123 234 ，那么第一个组合(0,1,2)和第二个组合(1,2,3)相比，有共同的元素(1,2)，仅有0,3不同，所以可得，如果第一个组合的和为sum，那么第二个组合的sum应该为第一个的sum加上(3-0)，即第二个组合的最后一个值与第一个组合的第一个值的差值。

编辑于 2017-04-25 20:21:13 回复(2)
paper头像 paper
这题测试用例好像有多组，使用scanf("%d%d%d", &n, &t, &c)会提示：
答案错误:您提交的程序没有通过所有的测试用例  
测试用例:  
对应输出应该为:  
17728
改为while(scanf("%d%d%d", &n, &t, &t) != EOF) {...}后通过
发表于 2015-09-26 01:17:51 回复(0)
Aurora1头像 Aurora1 
while 1:
    try:
        s1 = raw_input()
        s2 = raw_input()
    except:
        break
    n, t, c = map(int, s1.split())
    w = map(int, s2.split())
    m, s = 0, 0
    for i in range(0, n - c + 1):
        if i == 0:
            for j in range(c):
                m += w[j]
        else:
            m = m - w[i - 1] + w[i + c - 1]
        if m <= t:
            s += 1
    print s

发表于 2017-04-30 12:03:07 回复(0)
滚来吧，Offer君头像 滚来吧，Offer君 
注意 如果返回结果中有空的测试用例，可能是因为没有循环输入参数，我的代码（C++）

#include "iostream"
#include<vector>

using namespace std;

int main() 
{
	int n,t,c;
	while (cin>>n>>t>>c) {
		if(c>n || c<0)
			return -1;
		vector<int> num(n,0);
		int m = 0;
		while(m<n && cin>>num[m]) m++;
		
		int i = 0,j = 0;
		int sum = num[0], count = 1;
		int ret = 0;

		while(i <= n-c && j < n) {
			if(count == c && sum <= t)
				ret++;
			while(i <= n-c && (count > c || sum > t))
			{
				sum -= num[i];
				i++;
				count--;
				if(count == c && sum <= t)
					ret++;
			}
			if(j == n-1)
				break;
			j++;
			sum+=num[j];
			count++;
		}

		cout<<ret<<endl;
	}
	return 0;
}

已经ＡＣ

发表于 2015-09-26 10:27:19 回复(2)
程序远头像 程序远
滑动窗口机制。 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

int main(int argc, char** arg){
	int n, t, c;
	while (cin >> n >> t >> c){
		vector<int> a(n);
		for (int i = 0; i < n; i++){
			cin >> a[i];
		}
		int result = 0;
		int sum = 0;
		for (int i = 0; i <c; i++){
			sum += a[i];			
		}
		if (sum <= t){
			result++;
		}
		for (int i = c; i < n; i++){
			sum -= a[i - c];
			sum += a[i];
			if (sum <= t){
				result++;
			}
		}
		cout << result << endl;
	}
	return 0;
}

发表于 2015-09-27 18:30:11 回复(8)
CrazyCodingGirl头像 CrazyCodingGirl 
#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int n, t, c;
	while (cin >> n >> t >> c)
	{
		int count = 0, at = 0;
		vector<int> ai(n, 0);
		for (auto &i:ai)
			cin >> i;
		for (int i = 0; i < c; i++)
			at += ai[i];
		if (at <= t)
			count++;
		for (int i = c; i < n; i++)
		{
			at = at - ai[i - c] + ai[i];
			if (at <= t)
				count++;
		}
		cout << count << endl;
	}

	return 0;
}

发表于 2017-06-17 21:28:56 回复(0)
牛客606064号头像 牛客606064号
import java.util.*;
/**
 * C市现在要转移一批罪犯到D市，C市有n名罪犯，按照入狱时间有顺序，另外每个罪
 * 犯有一个罪行值，值越大罪越重。现在为了方便管理，市长决定转移入狱时间连续
 * 的c名犯人，同时要求转移犯人的罪行值之和不超过t，问有多少种选择的方式？
 * @author 
 *
 */

public class Main {
public static void main(String args[])
{
Scanner ss=new Scanner(System.in);
        Main b=new Main();
while(ss.hasNext())
{
int n=ss.nextInt();
int t=ss.nextInt();
int c=ss.nextInt();
int data[]=new int[n];
for(int i=0;i<n;i++)
{
data[i]=ss.nextInt();
}
int result=b.number(data, c, t);
System.out.println(result);
}
}
public int number(int data[],int c,int t)
{
int result=0;
int temp=0;
if(c==data.length)
{
result=1;
}
else
{
for(int i=0;i<c;i++)
{
temp=temp+data[i];
}
if(temp<=t)
{
result++;
}
for(int i=c;i<data.length;i++)
{
temp=temp+data[i]-data[i-c];
if(temp<=t)
{
result++;
}
}
}
return result;
}

}
已经通过，这个测试需要输入多个测试用例，在最外边添加一个while...
发表于 2015-09-26 19:06:21 回复(2)
recuerdos头像 recuerdos 
import java.util.Scanner;
 
public class Main {
    public static void main(String args[]){
        int n,t,c;
        Scanner scan = new Scanner(System.in);
        while(scan.hasNextInt()){
            n=scan.nextInt();
            t=scan.nextInt();
            c=scan.nextInt();
            int[] a=new int[n];
            
                for(int i=0;i<n;i++){
                    a[i]=scan.nextInt();
                }
            
        }
    }
    public static int xunzhao(int[] a,int c,int t){
        int n=a.length;
        int count = 0;
        int i,j,k;
        int sum=0;
        for(k=0;k<c;k++){
            sum+=a[k];
        }
        if(sum<=t){
            count++;
        }
        for(i=1;i<n-c+1;i++){
             
            j=i+c-1;
            sum=sum-a[i-1]+a[j];
            if(sum<=t){
                count++;
            }
             
        }
        System.out.print(count);
        return count;  
    }
}
答案错误:您提交的程序没有通过所有的测试用例  

测试用例:  
86530 3687600 26340  

对应输出应该为:  
60191

求解....
发表于 2015-09-26 17:05:44 回复(5)
芝麻开花头像 芝麻开花 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
	int n,t,c,number=0,sum=0;
	int i;
	int start,end;
	while (scanf("%d %d %d",&n,&t,&c)!=EOF)
	{
		int *arr=new int[n];
		start=0;
		for (i=0;i<n;i++)
		{
			scanf("%d",&arr[i]);
			if(i<c)
			{
				sum=sum+arr[i];
			}
		}
		end=c-1;
		do{
			if(sum<=t)
				number++;
			sum=sum+arr[end+1]-arr[start];
			end++;
			start++;
		}while(end<n);
		printf("%d\n",number);
		delete []arr;
	}
	return 0;
}

发表于 2015-09-28 17:15:52 回复(0)
yhan219头像 yhan219 
import java.util.Scanner;
import java.io.BufferedInputStream;
 
public class Main {
        public static void main(String args[]){
    	    Scanner in=new Scanner(new BufferedInputStream(System.in));
            int n=in.nextInt();
            int t=in.nextInt();
            int c=in.nextInt();
            int A[]=new int[n];
            int max=0;//记录连续C个数的值
            int re=0;//记录结果
            for(int i=0;i<n;i++){
                int now=in.nextInt();
                if(i<c){
            		max+=now;//前C个数赋给max
                }
                A[i]=now;
            }
            if(max<=t){
                re=1;
            }
            for(int i=c;i<n;i++){
                if((A[i]+max-A[i-c])<=t){
            		max=A[i]+max-A[i-c];
            		re++;
                }
            }
            System.out.println(re);
            in.close();
	}
}

编辑于 2015-09-25 23:10:02 回复(5)
pein531头像 pein531
其实就是给定一个长度为n的数组，求长度为c的所有子数组中，有多少个和是小于等于t的，用前缀和做就行。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null) {
            String[] params = line.trim().split(" ");
            int n = Integer.parseInt(params[0]);
            int t = Integer.parseInt(params[1]);
            int c = Integer.parseInt(params[2]);
            String[] strArr = br.readLine().trim().split(" ");
            int[] arr = new int[n];
            long[] calSum = new long[n];      // 构建前缀和数组
            for(int i = 0; i < n; i++){
                if(i == 0){
                    arr[i] = Integer.parseInt(strArr[i]);
                    calSum[i] = arr[i];
                }else{
                    arr[i] = Integer.parseInt(strArr[i]);
                    calSum[i] = calSum[i - 1] + arr[i];
                }
            }
            int count = 0;
            for(int i = -1; i < n - c; i++)
                if(calSum[i + c] - (i >= 0? calSum[i]: 0) <= t) count ++;
            System.out.println(count);
        }
    }
}


发表于 2021-02-26 12:21:21 回复(0)
Python
TimeMac头像 TimeMac 
while True:
    try:
        n, t, c = map(int, input().split())
        a = list(map(int, input().split()))
        temp_sum = sum(a[:c])
        res = 1 if temp_sum <= t else 0
        for i in range(n - c):
            temp_sum += a[i + c] - a[i]
            if temp_sum <= t:
                res += 1
        print(res)
    except Exception:
        break
编辑于 2019-05-05 23:57:01 回复(0)
Java
debuggor头像 debuggor 
 import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int t = sc.nextInt();
            int c = sc.nextInt();
            int[] arr = new int[n];
            int count = 0;
            int temSum = 0;
            for (int i = 0; i < c; i++) {
                arr[i] = sc.nextInt();
                temSum = temSum + arr[i];
            }
            for (int i = c; i < n; i++) {
                if (temSum <= t) {
                    count++;
                }
                arr[i] = sc.nextInt();
                temSum += arr[i];
                temSum -= arr[i - c];
            }
            if (temSum <= t) {
                count++;
            }
            System.out.println(count);
        }
    }
}

编辑于 2018-09-30 10:04:44 回复(0)
K-_-!!623头像 K-_-!!623
//***** 这么简单一道题 又没有讲明要循环输入 搞到卡了这么久
//主要用到滑动窗口
#include <iostream>
#define MAXSIZE 200000
using namespace std;

int main () {
    int crim[MAXSIZE]={0};
    int n,t,c;
    while (cin>>n>>t>>c) {
        for (int i=0;i<n;i++)
            cin>>crim[i];
        int sum=0;
        for (int i=0;i<c;i++) {
            sum=sum+crim[i];
        }
        int count;
        if (sum<=t)
            count=1;
        else
            count=0;
        int i=c;
        while (i<n) {
            sum=sum+crim[i]-crim[i-c];
            if (sum<=t)
                count=count+1;
            i++;
        }
        cout<<count<<endl;
     }
    return 0;
}

发表于 2018-03-26 16:59:46 回复(1)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>

using namespace std;

int main()
{     int n,t,c;     int a[200010];      while(cin>>n>>t>>c)     {         int sum=0,count=0;         for(int i=0;i<n;i++)             cin>>a[i];         if(c > n)             continue;         for(int i=0;i<c;i++)             sum += a[i];         if(sum <= t)             count++;         for(int i=c;i<n;i++)         {             sum -= a[i-c];             sum += a[i];             if(sum <= t)                 count++;         }         cout<<count<<endl;     }     return 0;
}

发表于 2017-12-01 00:32:16 回复(0)
C/C++
void12头像 void12 
#include<iostream>
#include<vector>
using namespace std;
int n, t, c;
//从k开始，连续往前找c个位置
int sum;
int cnt;
int flag;
int slider(int k, int c, vector<int> a) {
    sum = 0;
    cnt = 0;
    while (cnt < c) {
        sum = sum + a[k];
        k--;
        cnt++;
    }
    return sum;
}
int main() {
    //freopen("Text.txt", "r", stdin);
    while (cin >> n >> t >> c) {
        vector<int> a(n + 1);
        flag = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = n; i>=c; i--) {
            if (slider(i, c, a) <= t) {
                flag = 1;
                cout << i - c + 1 << endl;
                break;
            }
        }
        if(flag != 1) cout << 0 << endl;
    }
    return 0;
}

一开始的思路是，

既然题目已经给出罪犯的罪行等级是按照从小到大来排列的，那么只需要从大到小找连续相邻的c个罪犯，如果满足其和小于等于t,即表示该序列符合题意，那么从该点开始向左，所有的组合就一定都满足。此时无需继续向左分片搜索，而可以直接得出分组数目为当前下标-c+1。

但是提示超时。
后来参考了评论区的“滑块”思想，如下所示：

#include<iostream>
#include<vector>
using namespace std;
int n, t, c;
int main() {
    while (cin >> n >> t >> c) {
        vector<int> a(n + 1);
        int sum = 0;
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            if (i <= c) sum += a[i];
        }
        if(sum <= t) cnt++;
        for (int i = 1; i <= n - c; i++) {
            sum += a[i + c] - a[i];//滑块
            if (sum <= t) cnt ++;
           // else break;//此处不能break,为什么？
        }
        cout << cnt << endl;
    }
    return 0;
}
发表于 2017-08-22 09:39:58 回复(0)
wangwenbin头像 wangwenbin 

	importjava.util.Scanner;





	publicclassMain{





	    publicstaticvoidmain(String[] args){





	        Scanner sc = newScanner(System.in);





	        while(sc.hasNext()){





	            intn = sc.nextInt();





	            intt = sc.nextInt();





	            intc = sc.nextInt();





	            int[] time = newint[n];





	            for(inti=0;i<n;i++){





	                time[i] = sc.nextInt();





	            }





	            System.out.println(calNum(n, t, c, time));     





	        }





	    }





	    publicstaticintcalNum(intn, intt, intc, int[] time){





	        if(n<c)return0;





	        intnum = 0;





	        intsum = 0;





	        for(inti=0;i<c;i++){





	            sum+=time[i];





	        }





	        if(sum<=t)num++;





	        for(inti=c;i<n;i++){





	            sum += time[i] - time[i-c];





	            if(sum<=t)





	                num++;





	        }





	        returnnum;





	    }





	}

发表于 2017-08-08 18:24:18 回复(0)
提交观点

问题信息

动态规划
来自：百度2016研发工程师...
难度：
181条回答 34486浏览

热门推荐

通过挑战的用户

查看代码

相关试题

罪犯转移

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号