C市现在要转移一批罪犯到D市，C市有n名罪犯，按照入狱时间有顺序，另外每个罪犯有一个罪行值，值越大罪越重。现在为了方便管理，市长决定转移入狱时间连续的c名犯人，同时要求转移犯人的罪行值之和不超过t，问有多少种选择的方式（一组测试用例可能包含多组数据，请注意处理）？
[编程题]罪犯转移
主要思路是使用数组保存计算结果，减少计算次数，说得好听点就是所谓的动态规划
import java.util.*;
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(),t = in.nextInt(),c = in.nextInt();
int[]crime = new int[n];
int[] dp = new int[n];//保留求和值
for(int i = 0;i<n;i++)
{
crime[i] = in.nextInt();
if(i == 0) //边界值
{
dp[i] = crime[i];
}
else if(i<=(c-1))
{
dp[i] = dp[i-1]+crime[i];
}
else
{
dp[i] = dp[i-1]+crime[i]-crime[i-c];
}
if(i>=(c-1) && dp[i]<=t)
count++;
}
System.out.println(count);
}
}
}
发表于 2021-09-06 23:34:29
回复(0)
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)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
int t = in.nextInt();
int c = in.nextInt();
int[] weights = new int[n];
int i = -1;
while(++i<n && in.hasNext()){
weights[i] = in.nextInt();
}
int way = 0, sum = 0;
for(int j=0; j<c; j++){
sum += weights[j];
}
if (sum<=t) {
way++;
}
for(int j=1; j<=n-c; j++){
sum += weights[j+c-1] - weights[j-1];
if (sum<=t) {
way++;
}
}
System.out.println(way);
}
}
}
发表于 2017-08-01 17:03:37
回复(0)
此题主要是抓住 转移入狱时间连续的罪犯 这一条件，那么我们在累加可能的转移方式时候，只要满足不超过罪行总值，就可以把罪犯往后挪一位（当然为了保证人数不变，前面第一个罪犯就得去除），以此来计算满足条件的所有可能情况。
发表于 2017-03-10 13:29:15
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n,t,c;
int criminal[];
while(in.hasNext()){
n = in.nextInt();
t = in.nextInt();
c = in.nextInt();
criminal = new int[n];
for (int i = 0; i < n; i++){
criminal[i] = in.nextInt();
}
int count = 0;
int sum = 0;
for (int i = 0; i < c; i++){
sum += criminal[i];
}
for (int i = 0; i <= n - c; i++){
if (t >= sum){
count++;
}
if (i == n - c) break;
sum -= criminal[i];
sum += criminal[i + c];
}
System.out.println(count);
}
}
}
发表于 2016-09-15 20:02:31
回复(0)
//先计算前n项罪犯的罪行和sum[n+1]，当需要求某一连续区间[i,j]的总和时，只需要用sum[j] - sum[i]即可。
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[] weight = new int[n];
for (int i = 0; i < n; i++) {
weight[i] = sc.nextInt();
}
calWeight(n, t, c, weight);
}
}
private static void calWeight(int n,int t,int c,int[] weight){
int count = 0;
//先计算前n项和的数组
int [] sumN = new int[n + 1];
sumN[0] = 0;
for(int i = 1;i<=n;i++){
sumN[i] = sumN[i - 1] + weight[i - 1];
}
for(int j = c;j<=n;j++){
if(sumN[j] - sumN[j - c] <= t){
count++;
}
}
System.out.println(count);
}
}
发表于 2016-09-05 10:09:22
回复(0)
import java.util.Scanner;
/**
* 数组平移的思想真的很好
*
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
int t = in.nextInt();// 总和
int c = in.nextInt();
int p = 0;
int[] a = new int[n];
while (p < n) {
a[p] = in.nextInt();
++p;
}
int result = 0;
int sum = 0;
for (int i = 0; i < c; i++) {
sum += a[i];
}
if(sum<t){
result++;
}
for (int j = c; j < n; j++) {
sum += a[j] - a[j - c];//数组平移的思想
if (sum <=t) {
result++;
}
}
System.out.println(result);
}
}
}
发表于 2016-09-02 08:41:12
回复(0)
import java.util.Scanner;
public class Main{
//普通的思路就不多说了，时间复杂度肯定高，不能在规定时间内完成，
//我说一个我个人的O（n）的算法，只需要一次从左到右就可以计算出结果
//首先找一行数 1 2 3 4 5 6 7 8 9，
//这串数字总长9，假设最大和为20，找连续四个数的和，且不超过20
//这里我们需要两个指针，首先第一个指针指向数字1，让他从左到右一次累加前四个数
//也就是第一个指针指向了数字4；
//然后判断这个数是否小于20，如果小于20，结果集加1；
//然后第一个指针继续往下走一步，指向数字5，并且加上当前的数字，
//这时候就需要用第二个指针了，第二个指针指向数字1
//然后我们用当前的和减去第一个指针指向的数字1，
//然后判断和的大小，以此类推，第一个指针走一步，
//同时第二个指针也跟着走一步，一直保持第一个指针和第二个指针的间隔为
//需要累加的数字个数减1，累加的终止条件就是第一个指针走到末尾。
//以上就是算法的思路，下面看代码
public int criminal(int[] people ,int max , int limit){
//people是数组，max表示罪行值，limit表示连续的c名犯人。
//i表示第一个指针 ，count用来存储累加的和，
//result记录最后有多少种方法，temp记录limit的值
int i = 0 ,count = 0 , j = 0 , result = 0 , temp = limit;
//终止条件：i走到末尾
while(i<people.length){
//i从0开始。如果i小于转移犯人数，依次累计罪行值
while(i<temp){
count+=people[i];
i++;
}
if(limit-i==0){
//如果i是从0开始计算的，不减数
}else{
//否则，如果i已经累加完成过一次。count需要减去之前的开始罪行值
//因为每次只减去一个，所以第二个指针需要下移一位。
count = count - people[j];
j++;
}
//判断count的值是否小于等于最大罪行值，如果满足，结果集加1
if(count<=max){
result++;
}
//temp+1，之所以temp需要加1是因为，每次i在往后移动，
//如果temp的值保持不变，就只能累加一次，陷入死循环，
//所以必须保证i每次能够前进一步。所以temp需要同时+1；
//但是不用考虑temp的终止条件，她的值肯定最后是等于数组长度的。
temp++;
}
return result;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
do{
int len = sc.nextInt() ;
int max = sc.nextInt();
int limit = sc.nextInt();
int[] people =new int[len];
for(int i = 0 ; i < len ; i++){
people[i] = sc.nextInt();
}
int index = criminal(people,max,limit);
System.out.println(index);
}while(sc.hasNext());
}
}
编辑于 2016-08-24 10:38:21
回复(0)
一开始担心计算量问题，但是仔细一研究就会发现，题目要求连续的犯人，所以待帅选的组合的数目本来就是非常少的，有n-c+1个，完全可以一个个求是否满足题设要求进行排除。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.File;
import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.Arrays;
public class Main{
public static void main(String[] args) throws Exception
{
BufferedReader readin = new BufferedReader(new
InputStreamReader(System.in));
String settingLine = null;
while((settingLine = readin.readLine())!=null){
String crimeScoresLine = readin.readLine();
String[] settingParas = settingLine.split("
");
int n = Integer.parseInt(settingParas[0]);
int t = Integer.parseInt(settingParas[1]);
int c = Integer.parseInt(settingParas[2]);
ArrayList<Integer> crimeScoresList = new
ArrayList<Integer>();
for(String cs: crimeScoresLine.split(" ")){
crimeScoresList.add(Integer.parseInt(cs));
}
//System.out.println(Arrays.toString(crimeScoresLine.split("
")));
if(c==0){
System.out.println(0);
}
if(c<0){
throw new Exception();
}
int availCount = 0;// the count of possible combination
int crimeScoresSum = 0;
for(int i=0; i<c; ++i){
crimeScoresSum += crimeScoresList.get(i);
}
if(crimeScoresSum <= t){
availCount += 1;
}
int begin = -1;
int end = -1;
for(int i=1; i<n-c+1; ++i){
begin = i;
end = i+c-1;
crimeScoresSum += crimeScoresList.get(end);
crimeScoresSum -= crimeScoresList.get(begin-1);
if(crimeScoresSum <= t){
availCount += 1;
}
}
System.out.println(availCount);
}
}
}
发表于 2016-08-10 02:22:53
回复(0)
DP 也是可以过的。不过多了个数组
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String[] temp1 = sc.nextLine().split(" ");
int n =Integer.parseInt(temp1[0]);
int t =Integer.parseInt(temp1[1]);
int c =Integer.parseInt(temp1[2]);
int[] nums = new int[n];
String[] temp2 = sc.nextLine().split(" ");
for(int i = 0 ; i < n ; i ++){
nums[i] = Integer.parseInt(temp2[i]);
}
int start = 0,ret = 0;
int[] dp = new int[n];
dp[0] = nums[0];
for(int i = 1 ; i < n ; i ++){
dp[i] += dp[i-1]+ nums[i];
//large than t
while(dp[i] > t ){
dp[i] -= nums[start ++];
}
if(i - start + 1 == c){
ret ++;
dp[i] -= nums[start ++];
}
}
System.out.println(ret);
}//while
}//main
发表于 2016-08-03 10:27:43
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-11-14 18:20:31 -
2022-09-20 18:10:11
-
2022-09-19 17:24:24 -
2022-09-14 16:32:59
-
2022-09-13 13:27:01
相关试题
-
评论(148) 来自百度2016研发工程师在...
-
评论(178) 来自百度2016研发工程师在...
-
评论(169) 来自百度2016研发工程师在...
-
评论(1)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
