题目描述

有 $n$ 个箱子，第 $i$ 个箱子一开始有 $a_i$ 个球，进行最多 $k$ 次操作，每次操作可以从一个箱子拿走一个球或者放入一个球。第 $i$ 个箱子最多能装 $w_i$ 个球。如果一个箱子为空，就不能从里面拿球。
设相邻箱子的球的数量的差的平方中的最大值为 $x$ ，求进行最多 $k$ 次操作之后 $x$ 最小可以是多少。

方法一贪心+模拟

解题思路

一个比较直接的思路是使用模拟的方法，结合贪心思想解答。在k次操作中，每次操作只能减少或增加某个箱子的仅一个球，这为模拟提供了可能。
在每次操作时，根据贪心的思想，先找到相邻两个数差值最大的地方，然后分为三种情况分别模拟：

图片说明

接下来，以最大差值处 $a[i+1]>a[i]$ 时为例，如果进行操作来增大 $a[i]$ 或者减少 $a[i+1]$ 。最大差值处 $a[i+1]<a[i]$ 与此类似。

图片说明

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 取球放球
     * @param n int整型 箱子个数
     * @param k int整型 最多操作次数
     * @param a int整型vector 箱子内的球的个数
     * @param w int整型vector 箱子容量
     * @return int整型
     */
    int solve(int n, int k, vector<int>& a, vector<int>& w) {
        // 进行k次操作
        for(int i = 0; i < k; i++){
              // 先计算当前相邻差平方值最大的下标
              vector<int> dp(n - 1, 0); // 记录相邻两个数组之差的辅助数组
              int index = -1;
              int maxdis = 0;
              for(int i = 0; i < n - 1; i++){
                  dp[i] = a[i + 1] - a[i];
                  if(dp[i] * dp[i] > maxdis){
                      maxdis = dp[i] * dp[i];
                      index = i;
                  }
              }
              // 相邻两个数之差均为0
              if(index == -1)
                  continue;
              // 相邻两数最大差处a[i+1] > a[i]，此时需要增大a[i]或减少a[i+1]
              if(dp[index] > 0){
                  // 如果a[i]无法增大，因为a[i+1] > a[i] > 0，所以一定可以减少a[i+1]
                  if(a[index] == w[index]){
                      a[index + 1]--;
                      continue;
                  }
                  // 边界情况：这两个数为最后两个数
                  if(index == n - 2){
                      // 前面一组差为负，减少a[i-1]
                      if(index - 1 >= 0 && dp[index - 1] < 0)
                          a[index]++;
                      else
                          a[index + 1]--;
                  }
                  // 边界情况：这两个数为前两个数
                  else if(index == 0){
                      // 后面一组差为负，减少a[i+1]
                      if(index + 1 <= n - 2 && dp[index + 1] < 0)
                          a[index + 1]--;
                      else
                          a[index]++;
                  // 这两个数为中间的两个数
                  } else{
                      // 后面一组差为负，减少a[i+1]
                      if(dp[index + 1] < 0)
                          a[index + 1]--;
                      else{
                          // 前面一组差为负，增加a[i]
                          if(dp[index - 1] < 0)
                              a[index]++;
                          // 这三组差都为正
                          else{
                              // 前面一组差值更大
                              if(dp[index - 1] < dp[index + 1])
                                  a[index + 1]--;
                              else
                                  a[index]++;
                          }
                      }
                  }
            // 相邻两数最大差处a[i+1] < a[i]，此时需要增大a[i+1]或减少a[i]
            } else{ 
                // 如果a[i+1]无法增大，因为a[i] > a[i+1] > 0，所以一定可以减少a[i]
                if(a[index + 1] == w[index + 1]){
                    a[index]--;
                    continue;
                }
                // 边界情况：这两个数为最后两个数
                if(index == n - 2){
                    // 前面一组差为正，减少a[i]
                    if(index - 1 >= 0 && dp[index - 1] > 0)
                        a[index]--;
                    else
                        a[index + 1]++;
                }
                // 边界情况：这两个数为前面两个数
                else if(index == 0){
                    // 后面一组差为负，减少a[i]
                    if(index + 1 <= n - 2 && dp[index + 1] < 0)
                        a[index]--;
                    else
                        a[index + 1]++;
                // 这两个数为中间的两个数
                }else{
                    // 后面一组差为正，增加a[i+1]
                    if(dp[index + 1] > 0)
                        a[index + 1]++;
                    else{
                        // 前面一组差为正，减少a[i]
                        if(dp[index - 1] > 0)
                            a[index]--;
                        // 这三组差值都为负
                        else{
                            // 前面一组差值更大
                            if(dp[index - 1] > dp[index + 1]) 
                                a[index]--;
                        else
                            a[index + 1]++;
                        }
                    }
                }
            }
        }
        int res = 0;
        for(int i = 0; i < n - 1; i++)
            res = max(res, (a[i + 1] - a[i]) * (a[i + 1] - a[i])); //找到最大值
        return res;
    }
};

复杂度分析

时间复杂度：需要进行 $k$ 次操作，每次操作需要遍历一次数组来找到相邻两数差值最大的地方 $O(n)$ ，所以时间复杂度为 $O(kn)$
空间复杂度：使用大小为 $O(n)$ 的数组记录相邻两数的差值，空间复杂度为 $O(n)$

方法二动态规划+二分答案

解题思路

这是一道最小最大值问题，可以使用二分答案的方法解答，即对每个数字 $mid$ ，检查 $k$ 次操作之后能否将最大距离缩小到 $mid$ 之内。相比方法一，方法二的写法更加简洁，
需要确定检查的方法，可以考虑动态规划。定义数组 $dp[i][j]$ ，表示考虑前 $i$ 个箱子，第 $i$ 个箱子的球的个数为 $j$ 并且的相邻箱子差的绝对值都不超过 $m$ 最少需要几次操作。
初始化条件： $dp[0][i]=abs(a[0]-i)$

状态转移为：第 $i+1$ 个箱子最少有的球的个数为 $max(0,j-mid)$ ，最多有的球的个数为 $min(w_{i+1},j+mid)$ 。
根据状态转移方程更新完 $dp$ 数组后， $dp[n-1][0..w_{n-1}]$ 即为最大距离不超过 $mid$ 的最小操作次数，比较此值与 $k$ 的大小即可判断 $mid$ 能否达到，然后可以进行进一步的二分。

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 取球放球
     * @param n int整型 箱子个数
     * @param k int整型 最多操作次数
     * @param a int整型vector 箱子内的球的个数
     * @param w int整型vector 箱子容量
     * @return int整型
     */
    int solve(int n, int k, vector<int>& a, vector<int>& w) {
        // 二分bound
        int l = 0, r = 500;
        int ans;
        // 用于check的dp数组
        int dp[105][505];
        // 开始二分
        while(l <= r){
            int mid = (r+l)>>1;
            // 初始化dp数组
            memset(dp, 0x3f, sizeof dp);
            for(int i = 0; i <= w[0]; ++i)
                dp[0][i] = abs(a[0]-i);

            // 更新dp数组
            for(int i = 0; i < n-1; ++i){
                for(int x = 0; x <= w[i]; ++x){
                    int down = max(0, x-mid);
                    int up = min(w[i+1], x+mid);
                    // 根据状态转移方程更新dp数组
                    for(int y = down; y <= up; ++y)
                        dp[i+1][y] = min(dp[i+1][y], dp[i][x]+abs(a[i+1]-y));
                }
            }

            // 找到最小操作次数
            int mi = dp[n-1][0];
            for(int i = 1; i <= w[n-1]; ++i)
                mi = min(mi, dp[n-1][i]);

            // 最大距离可以不超过mid，向下二分
            if(mi <= k)
                ans = mid, r = mid-1;
            // 最大距离超过了mid，向上二分
            else
                l = mid+1;
        }
        return ans*ans;
    }
};

复杂度分析

时间复杂度：二分次数为 $O(lg(maxw_i))$ ,每次二分需要三层循环，时间复杂度为 $O(n*(maxw_i)^2)$ ，所以总的时间复杂度为 $O(n*(maxw_i)^2*lg(maxw_i))$
空间复杂度：进行check的动态规划数组大小为 $O(n*(maxw_i))$ ，所以空间复杂度为 $O(n*(maxw_i))$

题解 | #取球放球#

题目描述

方法一 贪心+模拟

解题思路

代码示例

复杂度分析

方法二 动态规划+二分答案

解题思路

代码示例

复杂度分析

方法一贪心+模拟

方法二动态规划+二分答案