首页 > 代码库 > 罪犯转移问题
罪犯转移问题
题目描述
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
解法一：
这个解法是网友解法中赞最多的，也是一个群里好友提供的解法的思路
import java.util.Scanner;public class Main { public static void main(String[] argc) { Scanner input = new Scanner(System.in); while(input.hasNext()){ int N = input.nextInt(); int MAX = input.nextInt(); int C = input .nextInt(); int[] arr = new int[N]; int sum = 0,result = 0; for(int i=0;i<N;++i){ arr[i] = input.nextInt(); sum += arr[i];//在还没有循环进下边的if时，他表示的含义是前i项累加和，当循环进下边的if之后，这个sum每次在这里往后加一个，在下面的if里面把前面的减一个，这样这个sum一直包含的是c个数组元素的累加和（因为正好sum是前c个的累积和的时候进入到下边的循环的）， if(i >= C-1){//不大于等于c-1，都不让进入这个循环来判断sum if(i>=C)//这个是那种平常的状态 sum -= arr[i-C];// if(sum <= MAX)//如果大于等于c-1，并且不大于等于c，那就说明是第一个长度为c的子串，判断这时候的sum就可以了 ++result; } } System.out.println(result); } }}
这个解法比题后讨论的解法更好，在一个for循环中，添加了arr原始数组，生成的累加和不需要储存在一个变量中当时使用
具体思路：一直累计前n项，n从0开始，当这个n正好等于c的时候，说明他是最前边的那c个元素的和，直接比较她们的和是否大于t，
当继续向下循环的时候，每次的sum都等于sum和当前的arr里面的值相结合，再在if里面把前边的一个元素删掉 让sum还是包含c个元素的累加和
解法二：这个是我自己写的，更好理解一点，可是空间复杂度稍高。
思路：首先把前n项和保存进一个数组sum，不过这个数组包含n+1个元素，因为sum[0]表示前0个数的和为0，这样的话在后面要用到sum[j]-sum[j-c]的时候不需要考虑开始的那种特殊的情况， 这样每次用sum[j]-sum[j-c] (j从c到n一共n-c+1种可能) 把结果和t相比较
import java.util.Scanner;public class Main{ public static void main(String[] args){ Scanner in=new Scanner(System.in); while(in.hasNext()){ int count=0; int n = in.nextInt();//n个人 int t = in.nextInt();//犯罪值和上限 int c = in.nextInt();//连续c名 int[] a = new int[n]; for(int i = 0;i<n;i++){ a[i] = in.nextInt(); } int[] sum = new int[n+1]; sum[0]=0; for(int i=1;i<=n;i++){ sum[i]=sum[i-1]+a[i-1]; } for(int j=c;j<=n;j++){ if((sum[j]-sum[j-c])<=t){ count++; } } System.out.println(count); } }}
罪犯转移问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。