1-10书本分发

1、题目

Description

You are given N number of books. Every ith book has Pi number of pages. You have to allocate books to M number of students. There can be many ways or permutations to do so. In each permutation one of the M students will be allocated the maximum number of pages. Out of all these permutations, the task is to find that particular permutation in which the maximum number of pages allocated to a student is minimum of those in all the other permutations, and print this minimum value. Each book will be allocated to exactly one student. Each student has to be allocated at least one book.每一个学生只能分配连续出现的书本。

Input

The first line contains ‘T‘ denoting the number of testcases. Then follows description of T testcases:Each case begins with a single positive integer N denoting the number of books.The second line contains N space separated positive integers denoting the pages of each book.And the third line contains another integer M, denoting the number of studentsConstraints:1<= T <=70，1<= N <=50，1<= A [ i ] <=250，1<= M <=50，Note: Return -1 if a valid assignment is not possible, and allotment should be in contiguous order (see explanation for better understanding)

Output

For each test case, output a single line containing minimum number of pages each student has to read for corresponding test case.

Sample Input 1

1
4
12 34 67 90
2

Sample Output 1

113

2、题目理解

有N本书，每本书有P页，要分给M个学生，在所有分法中每个页数的最大值，再在这些最大值里面选最小值。

可以将问题抽象给定一个数组，和一个值k，数组分成k段。要求这k段子段和最大值最小。求出这个值。

可以转换为桶，桶的个数为M，桶能装x本书。最后求页数

3、方法

方法1：暴力法（超时）

暴力递归，如果只有一本书那就直接返回这本书的页数，如果桶的数量（m）等于1那么就把所有的书都放到这个桶里面，就是求和的意思。

在下面的for循环中，因为每一个学生只能分配连续出现的书本，所以进行了遍历，意思就是桶的深度从1到N，同时通过递归遍历不同桶的数量的时候不同深度的情况。

    /**
     *
     * @param arr 每一本书对应的页数
     * @param n 一共有多少本书
     * @param m 一共有多少个同学
     * @return ans
     */
    private static int par(int[] arr, int n, int m) {
        if (n == 1) return arr[0];
        if (m == 1) return sum(arr, 0, arr.length - 1);

        int best = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            best = Math.min(best, Math.max(par(arr, i+1, m - 1), sum(arr, i, n - 1)));
        }
        return best;
    }

    private static int sum(int[] arr, int i, int i1) {
        int sum = 0;
        for (int j = i; j < i1; j++) {
            sum += arr[j];
        }
        return sum;
    }

方法2：动态规划

• 明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

basecase：

• 桶的数量为1的时候，对应的结果就应该是求和
• 深度为1的时候，默认就是第一本

状态：

• 桶的数量M
• 桶的深度N

选择：

• 和暴力方法一样best = Math.min(best, Math.max(x, y));

dp数组含义：

• dp[i][j]其中的i是桶的数量，j是桶的深度

    private static int dyn(int[] arr, int n, int m) {
        int[][] dp = new int[m][n];
        int[] sum = new int[arr.length];
        //计算sum数组
        for (int i = 0; i < arr.length; i++) {
            if (i == 0) {
                sum[i] = arr[i];
            } else {
                sum[i] = sum[i - 1] + arr[i];
            }
        }
        //初始化basecase
        for (int i = 0; i < n; i++) {
            dp[0][i] = sum[i];
        }
        for (int i = 0; i < m; i++) {
            dp[i][0] = arr[0];
        }
        //动态规划计算
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                int best = Integer.MAX_VALUE;
                //进行选择
                for (int k = 0; k <= j; k++) {
                    best = Math.min(best, Math.max(dp[i - 1][k], sum[j] - sum[k]));
                }
                dp[i][j] = best;
            }
        }
        return dp[m - 1][n - 1];
    }

方法3：二分

getBucket是通过给定数组和每个桶的容量得到需要多少个桶，再进行二分查找，找到满足M的最小容量

这里涉及一个二分取左边界值的技巧

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意
    
    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

private static int binary(int[] arr, int n, int m) {
    Arrays.sort(arr);
    int right = 0;
    for (int i = 0; i < arr.length; i++) {
        right += arr[i];
    }

    int left = arr[n - 1];
    while (right >= left) {
        int mid = left + (right - left) / 2;
        int bucket = getBucket(arr, mid);
        if (bucket > m) {
            left = mid+1;
        } else if (bucket < m) {
            right = mid - 1;
        } else if (bucket == m) {
            right = mid - 1;
        }
    }

    return left;
}

private static int getBucket(int[] arr, int size) {
    int sum = 0;
    int bucket = 1;
    for (int i = 0; i < arr.length; i++) {
        if (sum + arr[i] <= size) {
            sum += arr[i];
        } else {
            bucket++;
            sum = arr[i];
        }
    }
    return bucket;
}

1-10书本分发

原文：https://www.cnblogs.com/lvgj/p/14237322.html