题解 | #取球放球#

题目：
将题目换成另一个说法就是有n个数，可以对这n个数调整k次，每次只能对一个数加一或者减一，调整过程中，保持 ，设相邻两数的差的平方中的最大值为x，求调整k次后，x最小是多少

方法一：贪心

最多调整k次，因此枚举k次
在开始一轮调整前，先用一个dst数组存储相邻两数的差值，,然后找出相邻两数差值的平方最大值以及最大值处的下标i,根据最大差值可能大于0和小于0，

• :说明两数递增，此时想要降低，需要减小或者增加

• :说明两数递减，此时想要降低,即增大,需要增大或者减小

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\
        //调整k次
        for(int j=0;j<k;j++){
            int[]dst=new int[n-1];//存储相邻箱子球数之差的数组
            int index=-1;
            int maxDst=0;
            for(int i=0;i<n-1;i++){
                dst[i]=a[i+1]-a[i];
                //每次调整完后更新最大差值，记录最大差值的下标
                if(dst[i]*dst[i]>maxDst){
                    maxDst=dst[i]*dst[i];
                    index=i;
                }
            }
            //此时最大差值为dst[index]=a[index+1]-a[index]
            if(index==-1){
                continue;
            }
            //如果拥有最大差值的两数是增大的，则减小差值有两种方法：a[index+1]--或者a[index]++
            if(dst[index]>0)
            {
                if(a[index]==w[index])//较小的那个球数已经达到箱子总数，无法增大
                {
                    a[index+1]--;//只能前者减小
                    continue;//跳回循环头部，寻找下一个最大差值绝对值
                }
                //如果是前后两组数需要额外判断边界
                //如果是前面两个数
                if(index==0){
                    if(index+2<=n-1&&dst[index+1]<0)//后面一组数在有效区间内而且后面一组数是递减,形成山峰，降低山峰
                        a[index+1]--;//山顶降低
                    else 
                        a[index]++;//为使得山坡平缓,拉高第一个数
                }
                //如果是后两个数
                else if(index==n-2){
                    if(index-1>=0&&dst[index]<0)//前面一组数在有效区间内而且前面是递减，则形成三个数形成山谷，拉高中间数
                        a[index]++;
                    else
                        a[index+1]--;
                }
                //中间两组数
                else{
                    //后面那组数递减，降低山峰
                    if(dst[index+1]<0)
                        a[index+1]--;
                    //前面那组递减，增高山谷
                    else if(dst[index-1]<0)
                        a[index]++;
                    else{//前面一组和后面一组数都递增(1,2,3组递增)，如果前面一组递增较为平缓，则降低a[index+1],使得1,2组趋于平缓
                        if(dst[index-1]<dst[index+1])
                            a[index+1]--;
                        else a[index]--;
                    }
                }
            }else//dst[index]=a[index+1]-a[index]<0,要增大dst[index]有两个方法，增大a[index+1]或者减小a[index]
            {
                if(a[index+1]==w[index+1]){
                    a[index]--;
                    continue;
                }
                if(index==0){
                    if(index+2>=0)//后一组数在有效区间内且有一个山谷，拉高山谷
                        a[index+1]++;
                    else
                        a[index]--;
                }
                else if(index==n-2){
                    if(index-1>=0&&dst[index-1]>0)//前一组数增加，形成山峰，降低山峰
                        a[index]--;
                    else
                        a[index+1]++;
                }
                //中间两个数
                else{
                    if(dst[index+1]>0)
                        a[index+1]++;
                    else if(dst[index-1]>0)
                            a[index]--;
                    else{
                        if(dst[index-1]>dst[index+1])//前一组减小得较为平缓，增加a[index+1]使得1,2组趋于平缓
                            a[index+1]++;
                        else a[index]--;
                        }
                    }
            }
        }
        int max=0;
        //找出差值平方最大值
        for(int i=0;i<n-1;i++){
            int dst=a[i+1]-a[i];
            max=Math.max(max,dst*dst);
        }
        return max;
    }
}

复杂度：
时间复杂度：次操作，每次操作只有一个轮的循环，
空间复杂度：辅助1数组的大小为,空间复杂度为
方法二：动态规划+二分查找

• 题目要求查找最小的差值数组中的最大差值（简称为），的取值范围在0-500之间，可以在这个区间内寻找操作k次的，如果为了得到差值需要操作的次数大于k，则应该大于，往区间右边查找，否则，可以更小，往区间的左边查找
• 定义二维数组,表示第i个箱子的球数为j时，而且前i个箱子中的相邻箱子球数差不超过mid时的最小操作次数，初始化数组，(每个箱子的最大操作次数不超过50000)
• 当差值数组中所有差值都不超过mid时，如果第i个箱子的球数为j,第i+1个箱子的球数x最少是,最多是,于是，从第i个箱子的状态推出第i+1个箱子状态的转移方程为: ,(第i+1个箱子有x个球的操作次数，与往第i个箱子里面加减球后的操作次数取最小值)
• 当操作完n个箱子后，第n个箱子的球数在（0<=i<n）,取最小操作次数

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
        //ai<=wi<=500,2<=n<=100,相邻箱子球数最大差值不超过500，在0-500之间二分查找操作次数等于k时的差值
        int l=0,r=500;
        int mid=0;
        while(l<r){
            mid=(l+r)/2;
            if(cal(n,k,a,w,mid)>k)l=mid+1;//差值应该更大，往右边找
            else r=mid;//差值可以更小，往左边找
        }return l*l;
    }
    int cal(int n,int k,int[]a,int[]w,int mid){
        //最多有100个箱子，一个箱子的球数不超过500
        int[][]dp=new int[101][501];
        //初始化dp[0][i]，第一个箱子的球数为i时所需要的操作次数为|i-a[0]|
        for(int i=0;i<=w[0];i++){
            dp[0][i]=Math.abs(i-a[0]);
        }
        for(int i=0;i<n-1;i++){
            //初始化1~n-1行
            Arrays.fill(dp[i+1],50000);
            for(int j=0;j<=w[i];j++){
                //下一个箱子的球数最少是max(0,j-mid)最多是min(j+mid,w[i-1])
                for(int x=Math.max(0,j-mid);x<=Math.min(j+mid,w[i+1]);x++){
                    dp[i+1][x]=Math.min(dp[i+1][x],dp[i][j]+Math.abs(x-a[i+1]));//第i+1个箱子有x个球的操作次数，与往第i个箱子里面加减球后的操作次数取最小
                }
            }
        }
        int res=dp[n-1][0];
        for(int i=1;i<=w[n-1];i++){
            res=Math.min(res,dp[n-1][i]);//取最小操作次数
        }
        return res;
    }
}

复杂度：
时间复杂度：二分查找的时间复杂度为 ,最外层循环n次，里面两层最差循环 ,总的时间复杂度为
空间复杂度：数组的大小，