题解 | #取球放球#

算法思想一：贪心

解题思路：

利用贪心思想，利用一个辅助数组每次操作前记录相邻两个数组之差，并找到差的最大值的下标。这种时候我们有两种选择：较大的那个数减少，或者较小的那个数增大，每次操作时需要盘旋小数和大数谁在前，需要判断边界，需要判断前后一个数更改谁使最大值最小。

dp记录相邻两个数组之差的辅助数组：

图解：

代码展示：

C++版本

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) {
        // write code here
        for(int i = 0; i < k; i++){  //k次调整
              //每次调整前计算当前相邻差平方值最大的下标
              vector 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;
                  }
              }
              if(index == -1)  //没找到
                  continue;
              if(dp[index] > 0){  //选择前面的数增大或后面的数减少
                  if(a[index] == w[index]){//比较容量，若是较小的数无法增大，则后面减少
                      a[index + 1]--;
                      continue;
                  }
                  if(index == n - 2){  //若为最后两个数
                      if(index - 1 >= 0 && dp[index - 1] < 0)
                          a[index]++;
                      else
                          a[index + 1]--;
                  }   
                  else if(index == 0){  //若为前两个数
                      if(index + 1 <= n - 2 && dp[index + 1] < 0)
                          a[index + 1]--;
                      else
                          a[index]++;
                  } else{  //中间两个数
                      if(dp[index + 1] < 0) //后面一组是减少的 直接index+1减少
                          a[index + 1]--;
                      else{
                          if(dp[index - 1] < 0) //前面一组是减少的,直接index-1增加
                              a[index]++;
                          else{ //三组都是增大的
                              if(dp[index - 1] < dp[index + 1])  //前面那组的增大趋势更大
                                  a[index + 1]--;
                              else
                                  a[index]++;
                          }
                      }
                  }
            } else{  //选择前面的数减少或后面的数增大
                if(a[index + 1] == w[index + 1]){//若是较小的数无法增大，则后面减少
                    a[index]--;
                    continue;
                }
                if(index == n - 2){  //若是最后两个数
                    if(index - 1 >= 0 && dp[index - 1] > 0)
                        a[index]--;
                    else
                        a[index + 1]++;

                }
                else if(index == 0){  //若是前两个数
                    if(index + 1 <= n - 2 && dp[index + 1] < 0)
                        a[index]--;
                    else
                        a[index + 1]++;
                }else{ //比较相邻三组
                    if(dp[index + 1] > 0)
                        a[index + 1]++; 
                    else{
                        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次操作，每次操作只有一个循环

空间复杂度：dp数组占用空间

算法思想二：动态规划+二分

解题思路：

对于数组每次都要找到相邻元素之差的平方的最大值，最终任务是最小化这个最大值，因此可以考虑用二分查找来找这个。
1、首先用 表示第 i 个箱子的球的个数为 j 且前 i 个箱子中相邻箱子差的绝对值都不超过 mid（二分法每次的中间值）最少需要的操作次数，那么第 i+1 个箱子最少有的球的公式为：，最多有的球的个数为：。
2、根据最小的操作次数和题目给出的 k 来改变二分边界，因为dp数组中 就是所有箱子中相邻差不超过 mid 的最小操作次数，要找的就是其中的最小值，如果这个数字小于 k ，边界左移，缩小查找范围，如果大于 k，边界右移

代码展示：

C++版本

class Solution {
public:
      int solve(int n, int k, vector<int>& a, vector<int>& w) {
            int l = 0, r = 500;
            int res = 0;
            int dp[101][501];
            while(l <= r){ //二分法检查相邻元素的绝对值全部是否小于等于mid
                int mid = (l + r) / 2;
                memset(dp, 0x3f, sizeof(dp)); //每次都要初始化
                for(int i = 0; i <= w[0]; i++)
                    dp[0][i] = abs(a[0] - i);
                for(int i = 0; i < n - 1; i++){
                    for(int j = 0; j <= w[i]; j++){
                        int mn = max(0, j - mid);
                        int mx = min(j + mid, w[i + 1]);
                        for(int z = mn; z <= mx; z++) //从最小到最大更新dp
                        dp[i + 1][z] = min(dp[i + 1][z], dp[i][j] + abs(a[i + 1] - z));
                    }
                }
                int now = dp[n - 1][0]; //更新
                for(int i = 1; i <= w[n - 1]; i++)
                    now = min(now, dp[n - 1][i]);
                if(now <= k){
                    res = mid;
                    r = mid - 1;
                }
                else 
                    l = mid + 1;
            }
            return res * res;
    }
};

复杂度分析

时间复杂度：二分查找时间，再加三层循环时间

空间复杂度：dp数组占用空间