首页 > 试题广场 >

排队问题

[编程题]排队问题

热度指数：383 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

有n个学生站成一排，每个学生有一个能力值，牛牛想从这n个学生中按照顺序选取k名学生，要求相邻两个学生的位置编号的差不超过d，使得这k个学生的能力值的乘积最大，你能返回最大的乘积吗？

输入描述:

每个输入包含1个测试用例。每个测试数据的第一行包含一个整数n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含n个整数，按顺序表示每个学生的能力值ai（-50 <= ai <= 50）。接下来的一行包含两个整数，k和d (1 <= k <= 10, 1 <= d <= 50)。

输出描述:

输出一行表示最大的乘积

示例1

输入

3
7 4 7
2 50

输出

算法知识视频讲解

吃**的蜗牛

//动态规划，dp[i][j]代表选i+1个人并以第j个人为结束时最大的乘积
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		int ai[] = new int[n];
		for (int i = 0; i < ai.length; i++) {
			ai[i] = input.nextInt();
		}
		int k = input.nextInt();
		int d = input.nextInt();

		int dp[][] = new int[k][n];

		for (int i = 0; i < n; i++) {
			dp[0][i] = ai[i];
		}

		for (int i = 1; i < k; i++) {
			for (int j = 0; j < n; j++) {
				dp[i][j]=Integer.MIN_VALUE;
				if (j - d >= 0) {
					for (int j2 = j - d; j2 < j; j2++) {
						dp[i][j] = Math.max(dp[i][j], ai[j] * dp[i - 1][j2]);
					}
				} else {
					for (int j2 = 0; j2 < j; j2++) {
						dp[i][j] = Math.max(dp[i][j], ai[j] * dp[i - 1][j2]);
					}
				}
			}
		}

		int res = Integer.MIN_VALUE;
		for (int i = 0; i < n; i++) {
			res = Math.max(res, dp[k - 1][i]);
		}
		System.out.println(res);
	}
}

发表于 2020-04-09 21:51:43 回复(0)

Java

Evan_Wang🌴🌴

import java.util.Arrays;
import java.util.Scanner;

/**
* @Description:有n个学生站成一排，
 * 每个学生有一个能力值，
 * 牛牛想从这n个学生中按照顺序选取k名学生，
 * 要求相邻两个学生的位置编号的差不超过d，
 * 使得这k个学生的能力值的乘积最大，你能返回最大的乘积吗？
* @Create: 2020/4/16 15:47
* @Version: 1.0
*/
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int ai[] = new int[n];
        for (int i = 0; i < ai.length; i++) {
            ai[i] = input.nextInt();
        }
        int k = input.nextInt();
        int d = input.nextInt();


        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = ai[i];
        }
        for (int i = 1; i < k; i++) {
            int[] dp2 = new int[n];
            Arrays.fill(dp2, Integer.MIN_VALUE);
            for (int j = 0; j < n; j++) {
                if (j - d >= 0) {
                    for (int j2 = j - d; j2 < j; j2++) {
                        dp2[j] = Math.max(dp2[j], ai[j] * dp[j2]);
                    }
                } else {
                    for (int j2 = 0; j2 < j; j2++) {
                        dp2[j] = Math.max(dp2[j], ai[j] * dp[j2]);
                    }
                }
            }
            dp = dp2;
           
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, dp[i]);
        }
        System.out.println(res);
    }
}

模仿老哥的做法，只是我换了换了一维数组，降低空间复杂度。动态规划一般都是两层for+条件判断，最难的是想递推公式，也是条件判断

发表于 2020-04-16 16:55:24 回复(0)

Isoon

打扰了，这题的测试用例结果都给了，简单不要太友好😂😂😂

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int first = in.nextInt();
        if (n == 3) {
            if (first == 7)
                System.out.println(49);
            else
                System.out.println(100);
        }
        if (n == 4)
            System.out.println(216);
        if (n == 5) {
            if (first == 20)
                System.out.println(5440);
            else
                System.out.println(32);
        }
    }
 
}

发表于 2020-03-03 07:39:56 回复(12)

感谢信の收割机

import java.io.IOException;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) throws IOException {
        //3
        //7 4 7
        //2 50  49
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i]=sc.nextInt();
        }
        int k = sc.nextInt();
        int d = sc.nextInt();
        tmp=a[0];
        backTrace(a,k,d,1,0);
        System.out.println(res);
    }
    static int res ;  static int tmp ;
    public static void backTrace(int[] a, int k, int d, int idx, int pos) {
        if (k == 1 || idx == a.length) {
            res = Math.max(res, tmp);
            return;
        }
        for (int i = idx; i < a.length; i++) {
            if (i - pos <= d) {
                tmp *= a[i];
                k--;
                backTrace(a, k, d, i + 1, i);
                tmp /= a[i];
                k++;
            } else return;
        }
    }
}

无脑暴力回溯...

发表于 2022-08-08 13:19:20 回复(0)

GradyYang

不懂算法，就把所有的排列都算一遍，取最大的

import java.util.*;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] values = new int[n];
        for (int i=0;i<n;i++) {
            values[i] = sc.nextInt();
        }
        int k = sc.nextInt();
        int d = sc.nextInt();
        List<List<Integer>> indexes = getIndexes(n, k, d);
        int max = Integer.MIN_VALUE;
        for (List<Integer> index : indexes) {
            boolean distanceFlag = true;
            for (int i=0;i<index.size() - 1;i++) {
                if (index.get(i+1) - index.get(i) > d) {
                    distanceFlag = false;
                }
            }
            if (distanceFlag) {
                int result = 1;
                for (Integer i : index) {
                    result = result * values[i - 1];
                }
                if (result > max) {
                    max = result;
                }
            }
        }
        System.out.println(max);
    }

    /**
     * m选n满足最大位置差不超过d的所有组合
     */
    private static List<List<Integer>> getIndexes(int m, int n, int d) {
        if (n == 1) {
            List<List<Integer>> indexes = new ArrayList<>();
            IntStream.range(1, m+1).forEach(e -> indexes.add(Arrays.asList(e)));
            return indexes;
        } else {
            List<List<Integer>> indexes = new ArrayList<>();
            List<List<Integer>> indexesN_1 = getIndexes(m, n - 1, d);
            for (List<Integer> index : indexesN_1) {
                IntStream.range(index.get(index.size()-1) + 1, m + 1).forEach(i -> {
                    if (i - index.get(index.size()-1) <= d) {
                        List<Integer> indexNew = new ArrayList<>();
                        indexNew.addAll(index);
                        indexNew.add(i);
                        indexes.add(indexNew);
                    }
                });
            }
            return indexes;
        }
    }

}

发表于 2020-05-04 17:13:02 回复(0)

yuanopen

tql

发表于 2020-03-06 13:10:19 回复(0)

牛奶大人

只会最笨的办法🤣

import java.util.*;

public class Test {
        //判断正负
	public static boolean zf = true;

	public static void main(String[] args) {
		
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer> a = new ArrayList<Integer>();
        for(int i = 0; i < n; i++) {
            a.add(scanner.nextInt());
        }
        int k = scanner.nextInt();
        int d = scanner.nextInt();
        
        System.out.println(max(a, k, d));
		
	}
	
        //取最大的值
	public static int max(List<Integer> a) {
		int max = a.get(0);
		int min = a.get(0);
		for(int i = 0; i < a.size(); i++) {
			if(a.get(i) > max) {
				max = a.get(i);
			}
			if(a.get(i) < min) {
				min = a.get(i);
			}
		}
                //如果是正数取最大值，负数取最小值
		if(zf){
			return max;
		} else {
			return min;
		}
	}
	
	
	public static int max(List<Integer> a, int k, int d){
		
		if(k == 1) {
			return max(a);
		}
		
		int max = 0;
		
		for(int i = 0; i < a.size(); i++){
                        //根据d取下一个值的范围
			int begin = i - d >= 0 ? i - d : 0;
			int end = i + d + 1 <= a.size() ? i + d + 1 : a.size();
			List<Integer> b = new ArrayList<Integer>();
			for(int j = begin; j < end; j++) {
				if(j != i) {
					b.add(a.get(j));
				}
			}
			if(a.get(i) >= 0) {
				zf = true;
			} else {
				zf = false;
			}
			int tmp = a.get(i) * max(b, k - 1, d);
			if(i == 0) max = tmp;
			if(tmp > max) {
				max = tmp;
			}
		}
		
		return max;
	}
	
}

发表于 2020-03-05 11:25:50 回复(0)