[leetcode/lintcode 题解] 放小球问题
n个桶中小球的个数已知,可以操作k次(每次从桶中取出一个球,或者添加一个球),每个桶有规定的最大容量W[i]。求操作后两相邻桶之间的最大差值的平方的最小值。
在线评测地址:
https://www.lintcode.com/problem/put-small-balls/?utm_source=sc-js-mh0611
https://www.lintcode.com/problem/put-small-balls/?utm_source=sc-js-mh0611
样例 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。
【题解】
二分最大差值target，判断最大差值为target时的最小变动球数是否小于等于最多操作次数k。
如果最小变动球数小于等于k，那么说明可行，继续搜寻更小的差值;否则搜寻更大的差值。
计算最大差值为target时的最小变动球数：
对于数组A[]的每一个桶内小球数目，我们都需要进行[1,W[i]]范围内的可能状态的转移。
令dp[i][j]表示A[i]=j时，A[i]与A[i-1]差值不大于target所需要的最小变动球数。
当A[i]=j时，可行的A[i-1]的范围为[max(0, j - target)，min(W[i - 1], j + target)]。
当A[i]=j，k在[max(1, j - target)，min(100, j + target)]范围内时，我们可以写出以下式子：
临界值：
dp[0][j] = abs(j - A[0])
状态转移方程：
dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(j - A[i]))
最后在所有最后一位的可能解dp[n-1][?]中的最小值就是我们求的最小变动球数。
class Solution:
"""
@param n: the number of buckets
@param k: the maximum times of operations
@param A: the number of balls in each bucket
@param W: the maximum capacity of each bucket
@return: return the minimum square value of the maximum difference
"""
# 计算当相邻差值最大为target时的最小变动球数
def min_cost(self, n, A, W, target):
# dp[i][j]表示元素A[i]=j时，A[i]与A[i-1]差值不大于target所需要的最小变动球数
# 初始化为极大值
dp = [[1000000000] * 101 for _ in range(n)]
for i in range(n):
for j in range(W[i] + 1):
if i == 0:
# 临界值：第一个元素A[0]调整为j的变动球数
dp[0][j] = abs(j - A[0])
else:
# left为A[i]=j时，A[i-1]与A[i]差值不大于target的A[i-1]最小值
# right为A[i]=j时，A[i-1]与A[i]差值不大于target的A[i-1]最大值
left = max(0, j - target)
right = min(W[i - 1], j + target)
for k in range(left, right + 1):
# 当A[i-1]=k时，答案为A[i-1]=k的代价dp[i-1][k]，加上A[i]=j的调整代价abs(j-A[i])
dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(j - A[i]))
mincost = 1000000000
for i in dp[n - 1]:
mincost = min(mincost, i)
return mincost
def getAns(self, n, k, A, W):
ans = 1000000000
left, right = 0, 100
# 二分最大差值，用minCost计算最小变动球数
# 如果最小变动球数小于等于k，那么说明可行，继续搜寻更小的差值
# 否则搜寻更大的差值
while left + 1 < right:
mid = left + (right - left) // 2
if self.min_cost(n, A, W, mid) <= k:
ans = min(ans, mid)
right = mid
else:
left = mid
if self.min_cost(n, A, W, left) <= k:
ans = min(ans, left)
if self.min_cost(n, A, W, right) <= k:
ans = min(ans, right)
return ans*ans
更多语言代码参见：https://www.jiuzhang.com/solution/put-small-balls/?utm_source=sc-js-mh0611
