题解 | #取球放球#

思路：

题目的主要信息：

• 一共n个箱子，每个箱子有一定容量和一定初始球个数
• 进行k次操作，每次操作对某一个箱子中的球进行加1或者减1
• 求k次操作之后要使任意相邻箱子球数差的平方的最大值达到最小。

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

class Solution {
public:
      int solve(int n, int k, vector<int>& a, vector<int>& w) {
          for(int i = 0; i < k; i++){  //k次调整
              //每次调整前计算当前相邻差平方值最大的下标
              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;
                  }
              }
              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

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

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;
    }
};

复杂度分析：

• 时间复杂度：，二分法查找为log，内里最多的时间是三层循环
• 空间复杂度：，辅助数组dp