2020-06-13 18:04:45
问题描述：
n个桶中小球的个数已知,可以操作k次(每次从桶中取出一个球,或者添加一个球),每个桶有规定的最大容量W[i]。求操作后两相邻桶之间的最大差值的平方的最小值。
样例
样例 1:
输入:
5
6
[1,2,3,4,5]
[15,15,15,15,15]
输出:
0
说明
共有5个桶，最多操作6次，桶内的小球分别是1,2,3,4,5，桶的最大容量分别是15,15,15,15,15。
注意事项
n <= 100
W[i] <= 100
问题求解：
最大化最小的问题可以使用二分来解决。
主要问题就是check函数如何写，也就是对于最大差值mid，至少需要多少操作来完成。
dp[i][j] = 到了第i位置最大差值小于等于mid的最小操作。
public int getAns(int n, int k, List<Integer> A, List<Integer> W) {
int l = -1;
int r = -1;
for (int i = 1; i < A.size(); i++) r = Math.max(r, Math.abs(A.get(i) - A.get(i - 1)));
while (r - l > 1) {
int mid = l + (r - l) / 2;
if (check(A, mid, k, W)) r = mid;
else l = mid;
}
return r * r;
}
private boolean check(List<Integer> A, int mid, int k, List<Integer> W) {
int[][] dp = new int[101][101];
for (int i = 0; i < 101; i++) {
for (int j = 0; j < 101; j++) {
dp[i][j] = Integer.MAX_VALUE / 2;
}
}
for (int i = 0; i <= W.get(0); i++) dp[0][i] = Math.abs(i - A.get(0));
for (int i = 1; i < A.size(); i++) {
for (int curr = 0; curr <= W.get(i); curr++) {
for (int prev = 0; prev <= W.get(i - 1); prev++) {
if (Math.abs(curr - prev) > mid) continue;
dp[i][curr] = Math.min(dp[i][curr], dp[i - 1][prev] + Math.abs(curr - A.get(i)));
}
}
}
int res = Integer.MAX_VALUE / 2;
for (int i = 0; i <= W.get(A.size() - 1); i++) res = Math.min(res, dp[A.size() - 1][i]);
return res <= k;
}