【蓝桥杯】历届真题 分果果（省赛）Java
【问题描述】
小蓝要在自己的生日宴会上将 n 包糖果分给 m 个小朋友。
每包糖果都要分出去，每个小朋友至少要分一包，也可以分多包。
小蓝已经提前将糖果准备好了，为了在宴会当天能把糖果分得更平均一些，小蓝要先计算好分配方案。
小蓝将糖果从 1 到 n 编号，第 i 包糖果重 wi。
小朋友从 1 到 m 编号。每个小朋友只能分到编号连续的糖果。
小蓝想了很久没想出合适的分配方案使得每个小朋友分到的糖果差不多重。
因此需要你帮他一起想办法。
为了更好的分配糖果，他可以再买一些糖果，让某一些编号的糖果有两份。
当某个编号的糖果有两份时，一个小朋友最多只能分其中的一份。
请找一个方案，使得小朋友分到的糖果的最大重量和最小重量的差最小，请输出这个差。
例如，小蓝现在有 5 包糖果，重量分别为 6, 1, 2, 7, 9，如果小蓝要分给两个小朋友，则他可以将所有糖果再买一份，两个小朋友都分到 1 至 5 包糖果，重量都是 25，差为 0。
再如，小蓝现在有 5 包糖果，重量分别为 6, 1, 2, 7, 9，如果小蓝要分给三个小朋友，则他可以将第 3 包糖果再买一份，第一个小朋友分 1 至 3 包，第二个小朋友分 3 至 4 包，第三个小朋友分第 5 包，每个小朋友分到的重量都是 9，差为 0。
再如，小蓝现在有 5 包糖果，重量分别为 6, 1, 2, 7, 9，如果小蓝要分给四个小朋友，则他可以将第 3 包和第 5 包糖果再买一份，仍然可以每个小朋友分到的重量都是 9，差为 0。
再如，小蓝现在有 5 包糖果，重量分别为 6, 1, 2, 7, 9，如果小蓝要分给五个小朋友，则他可以将第 4 包和第 5 包糖果再买一份，第一个小朋友分第 1 至 2 包重量为 7，第二个小朋友分第 3 至 4 包重量为 9，第三个小朋友分第 4 包重量为 7，第四个和第五个小朋友都分第 5 包重量为 9。
差为 2。
【输入格式】
输入第一行包含两个整数 n 和 m，分别表示糖果包数和小朋友数量。
第二行包含 n 个整数 w1, w2, · · · , wn，表示每包糖果的重量。
【输出格式】
输出一个整数，表示在最优情况下小朋友分到的糖果的最大重量和最小重
量的差。
【样例输入】
5 2
6 1 2 7 9
【样例输出】
0
【样例输入】
5 5
6 1 2 7 9
【样例输出】
2
【评测用例规模与约定】
对于 30% 的评测用例，1 ≤ n ≤ 10，1 ≤ m ≤ 10，1 ≤ wi ≤ 10；
对于 60% 的评测用例，1 ≤ n ≤ 30，1 ≤ m ≤ 20，1 ≤ wi ≤ 30；
对于所有评测用例，1 ≤ n ≤ 100，1 ≤ m ≤ 50，1 ≤ wi ≤ 100。在评测数据
中，wi 随机生成，在某个区间均匀分布。
【思路与分析】
这道题难度对于我这样的小白来讲还是比较大的，只能品到要使用动态规划法来求解。动态规划方程的寻找和解题的具体过程还没品太明白，po出大佬的代码，希望对朋友们有所启发。
【代码】
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) { new Main().run(); }
int INF = 0x3F3F3F3F; //代表一个无穷大的常量，10^9级别
void run() {
//获取输入，类似于Scanner
InputReader in = new InputReader(System.in);
int n = in.readInt(), m = in.readInt(), ans = INF;
int[][][] dp = new int[m + 1][n + 1][n + 1]; //模拟将m包糖果分给n个人的过程
int[] S = new int[n + 1];
for (int i = 1; i <= n; i++)
S[i] = S[i - 1] + in.readInt();
for (int i = 0; i <= m; i++)
for (int j = 0; j <= n; j++)
for (int k = 0; k <= j; k++) dp[i][j][k] = INF;
dp[0][0][0] = 0;
for (int min = S[n] * 2 / m; min > 0; min--) {
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
int trans2 = 0, trans3 = 0;
for (int k = 1; k <= j; k++) {
dp[i][j][k] = dp[i][j][k - 1];
while (trans2 < k && S[j] - S[trans2 + 1] >= min &&
max(dp[i - 1][trans2 + 1][trans2 + 1], S[j] - S[trans2 + 1]) <= max(dp[i - 1][trans2][trans2], S[j] - S[trans2])) trans2++;
if (S[j] - S[trans2] >= min)
dp[i][j][k] = min(dp[i][j][k], max(dp[i - 1][trans2][trans2], S[j] - S[trans2]));
while (trans3 < k && S[j] - S[trans3 + 1] >= min &&
max(dp[i - 1][k][trans3 + 1], S[j] - S[trans3 + 1]) <= max(dp[i - 1][k][trans3 + 1], S[j] - S[trans3])) trans3++;
if (S[j] - S[trans3] >= min)
dp[i][j][k] = min(dp[i][j][k], max(dp[i - 1][k][trans3], S[j] - S[trans3]));
}
}
ans = min(ans, dp[m][n][n] - min);
}
System.out.println(ans);
}
//利用三元运算符得出最大、最小值
int max(int arg1, int arg2) { return arg1 > arg2 ? arg1 : arg2; }
int min(int arg1, int arg2) { return arg1 < arg2 ? arg1 : arg2; }
//输入类，也可以不使用内部类的方式进行声明
/*
BufferedReader = new BufferedReader(new InputStreamReader(System.in));
不使用内部类的话需要在main方法抛出 IOExcepiton 异常
*/
class InputReader {
BufferedReader reader;
StringTokenizer token;
InputReader(InputStream in) {
this.reader = new BufferedReader(new InputStreamReader(in));
}
String read() {
while (token == null || !token.hasMoreTokens()) {
try {
token = new StringTokenizer(reader.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return token.nextToken();
}
int readInt() { return Integer.parseInt(read()); }
}
}