题解 | #取球放球#

取球放球

问题描述：有n个箱子，第i个箱子一开始有a_i个球，你可以进行最多k次操作，每次操作可以从一个箱子拿走一个球或者放入一个球。第i个箱子最多能装w_i个球，装满了之后不能再往这个箱子里面放球。如果一个箱子为空，就不能从里面拿球。
设相邻箱子的球的数量的差的平方中的最大值为x，求进行最多k次操作之后x最小可以是多少。
示例
输入：5,4,[12,4,7,9,1],[15,15,15,15,15]
返回值：36
说明：5个桶，4次操作，桶内的小球分别是1,2,3,4,5 桶的最大容量都是15。第一次操作往第2个箱子放2个球，往第5个箱子放2个球得到[12,6,7,9,3],此时相邻箱子的球数差值为[-6,1,2,-6],平方后为[36,1,4,36]，其中最大值为36

方法一
思路分析
   根据题中所说可以通过贪心方法操作k次寻找相邻箱子的球的数量的差的平方中的最大值，设置辅助数组存储相邻箱子的球数差值，每次计算后获得相邻箱子的球数差值平方后的最大值，然后根据位置计算前后箱子的球如何操作，此时存在两种情况：

• 如果前面箱子的球数更大，则从前面的箱子取球，
• 如果前面箱子的球数更小，则往前面的箱子中放球
• 该方法的核心思想就是每次找到相邻箱子的球数差值的平方的最大值，然后根据这个最大值去减小相邻的箱子中的球

最后k次操作后，从箱子中计算出相邻箱子的球的数量的差的平方中的最大值。

图解

k次操作从箱子中计算出相邻箱子的球的数量的差的平方中的最大值

java核心代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 取球放球
     * @param n int整型 箱子个数
     * @param k int整型 最多操作次数
     * @param a int整型一维数组 箱子内的球的个数
     * @param w int整型一维数组 箱子容量
     * @return int整型
     */
    
    public int solve (int n, int k, int[] a, int[] w) {
        // write code here
        operation(n,k,a,w);//操作k次
		int res = 0;
		for(int j = 0; j < n - 1; j++)
		{
             int value = a[j + 1] - a[j];//计算相邻位置的差
             if(value * value > res)
			 { 
                 res = value* value;
                      
             }
        }
        return res;
    }
    public void operation(int n, int k, int[] a, int[] w)
    {
        for(int i = 0; i < k; i++)
        {
            int [] array = new int[n-1];  
            int ans = -1;
              int maxdis = 0;
              for(int j = 0; j < n - 1; j++){
                  array[j] = a[j + 1] - a[j];//计算相邻位置的差
                  if(array[j] * array[j] > maxdis){ 
                      maxdis = array[j] * array[j];
                      ans = j;//存储最大差的位置
                  }
              }
              if(ans == -1)  
                  continue;
              if(array[ans] > 0)
			  {  
                  if(a[ans] == w[ans])//这个位置的球达到最大值
				  {
                      a[ans + 1]--;
                      continue;
                  }
				  else if(ans == 0)//开始位置
				  {  
                      if(ans + 1 <= n - 2 && array[ans + 1] < 0)
                          a[ans + 1]--;
                      else
                          a[ans]++;
                  } 
                  if(ans == n - 2)//末尾位置
				  {  
                      if(ans - 1 >= 0 && array[ans - 1] < 0)
                          a[ans]++;
                      else
                          a[ans + 1]--;
                  }   
                  
				  else//中间位置
				  {  
                      if(array[ans + 1] < 0) 
                          a[ans + 1]--;
                      else{
                          if(array[ans - 1] < 0) 
                              a[ans]++;
                          else{ 
                              if(array[ans - 1] < array[ans + 1])  
                                  a[ans + 1]--;
                              else
                                  a[ans]++;
                          }
                      }
                  }
            } 
			else
			{  
                if(a[ans + 1] == w[ans + 1])
				{
                    a[ans]--;
                    continue;
                }
                if(ans == n - 2)
				{  
                    if(ans - 1 >= 0 && array[ans - 1] > 0)
                        a[ans]--;
                    else
                        a[ans + 1]++;

                }
                else if(ans == 0)
				{  
                    if(ans + 1 <= n - 2 && array[ans + 1] < 0)
                        a[ans]--;
                    else
                        a[ans + 1]++;
                }
				else
				{ 
                    if(array[ans + 1] > 0)
                        a[ans + 1]++; 
                    else{
                        if(array[ans - 1] > 0)
                            a[ans]--;
                        else{ 
                            if(array[ans - 1] > array[ans + 1]) 
                                a[ans]--;
                        else
                            a[ans + 1]++;
                        }
                    }
                }
            }
        } 
    }
};

复杂度分析

• 时间复杂度：两层嵌套循环，外层循环次数为$k$，内层循环次数为$n$，因此时间复杂度为$O(n*k)$
• 空间复杂度：借助于一个大小为$n-1$的辅助数组用于存储相邻箱子的球的数量的差，因此空间复杂度为$O(n-1)$

方法二
思路分析
    本题采用动态规划即自下而上的办法，设置辅助数组$array[i][j]$表示第i个箱子中球的个数为j时相邻箱子的球的数量的差的平方中的最大值小于某一值的最小操作次数，那么初始化$array[0][j]$，第一个箱子中球的个数为$0、1、2、...w[0]$时的操作个数为$abs(j-a[0])$。其状态转移方程，当前箱子球的个数为j，后一个箱子最少的球数$max(0, j-mid)$，后一个箱子最大的球数$min(j+mid, w[i-1])$，遍历这两个数确定第cur个箱子中球的个数为j最少的操作数。最后$array[n-1][0、1、2...w[n-1]]$中的一个就是需要操作的最小值

C++核心代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 取球放球
     * @param n int整型 箱子个数
     * @param k int整型 最多操作次数
     * @param a int整型vector 箱子内的球的个数
     * @param w int整型vector 箱子容量
     * @return int整型
     */
    int calc(int n, int k, vector<int>& a, vector<int>& w, int mid) {
       
        int cur = 0;
        for (int i = 0; i <= w[0]; i++) 
        {
            array[0][i] = abs(i-a[0]);//初始化第一个箱子的球的个数分别为0、1、2、3...w[0]需要的操作数
        }
        for (int i = 1; i < n; i++) 
        {
            cur ^= 1;
            for (int j = 0; j <= w[i]; j++) {
                array[cur][j] = k+1;
                int m_max=max(0, j-mid);//后一个箱子最少的球数
                int m_min= min(j+mid, w[i-1]);//后一个箱子最大的球数
                for (int k = m_max; k <=m_min; k++)
                {
                    array[cur][j] = min(array[cur][j], array[cur^1][k] + abs(j-a[i]));
                    //第cur个箱子中球的个数为j最少的操作数
                }
            }
        }
        int k_min = k+1;//当前操作次数+1
        for (int j = 0; j <= w[n-1]; j++) {
            k_min = min(k_min, array[cur][j]);
        }
        return k_min;
    }
    int array[100][500];
    int solve(int n, int k, vector<int>& a, vector<int>& w) {
        // write code here
        int left = 0, right = 500;
        while (left < right) 
        {
            int mid = (left+right) /2;
            if (calc(n, k, a, w, mid) > k) //返回值表示最大距离不超过mid的最小操作数
                left = mid + 1;//向上进一步二分
            else right = mid;//向下进一步二分
        }
        return left * left;
    }
};

复杂度分析

• 时间复杂度：二分查找的次数为，在内部进行的操作为三重嵌套循环，最大时间复杂度为$O(n*max(w[i])^2)$，因此总的时间复杂度为$O(\log k*n*max(w[i])^2)$
• 空间复杂度：借用一个大小为$n*max(w[i])$辅助数组，因此空间复杂度为$O(n*max(w[i]))$