题目描述
有n个箱子，第i个箱子一开始有ai?个球，你可以进行最多k次操作，每次操作可以从一个箱子拿走一个球或者放入一个球。第i个箱子最多能装wi?个球，装满了之后不能再往这个箱子里面放球。如果一个箱子为空，就不能从里面拿球。
设相邻箱子的球的数量的差的平方中的最大值为x，求进行最多k次操作之后x最小可以是多少。
输入
5,4,[12,4,7,9,1],[15,15,15,15,15]
输出
36
往第2个箱子放2个球，往第5个箱子放2个球得到[12,6,7,9,3],此时相邻箱子的球数差值为[-6,1,2,-6],平方后为[36,1,4,36]，其中最大值为36
【思路】
本题的问题是使得经过一定的次数，使得相邻的差值平方尽可能小（即：所有数尽可能靠近）
贪心策略：
每一轮找到相邻差值最大的那两个数a[index]=>a[index+1]，有两种策略：较大的那个数减少，或者较小的那个数增大。
具体的策略是：
如果当前a[index]<a[index+1]即 是增大的：分三大类情况：
- 当前index==0 第一二个数：那么分析其后一组是否为增大或减少，选择相应的策略
- 当前index==n-2 最后两个数index-2 index-1 那么分析前面一组是否为增大或减少，选择相应的策略
- 其它情况，需要同时分析前面一组，后面一组的情况，特别点（如三组都增大：需要比较斜率大小）
如果当前a[index]<a[index+1]即 是减少的 ，同上所述
优化策略：
由于有w[i]上限限制，当发现较小的那个数a[index]==w[index] 达到上限，那么直接较大的那个数减少即可。实现代码：
int solve(int n, int k, vector<int>& a, vector<int>& w) {for(int i=0;i<k;i++) //总共需要调整k次{//首先计算出当前相邻差值最大的indexvector<int> dst(n-1,0);int index=-1;int _max_dst=0;for(int i=0;i<n-1;i++){dst[i]=a[i+1]-a[i];//dst[i]if(dst[i]*dst[i]>_max_dst){_max_dst=dst[i]*dst[i];index=i;}}//那么 相邻值相差最大的为 a[index]和a[index+1]if(index==-1)continue;if(dst[index]>0) //若该组为增大 那么两种策略：前面的数增大 或者 后面的数减少{if(index==n-2) //如果这是最后两个数 0=>n-1 dst[n-2]=a[n-1]-a[n-2]{if(index-1>=0 && dst[index-1]<0) //如果前面一组是减少的{if(a[index]<w[index]) //优先选择当前Index++{a[index]++;} else{ //否则后面那个数 减少a[index+1]--;}} else{a[index+1]--;//那么直接最后那个数减少}}else if(index==0) //第一、二个数{if( (index+1<=n-2 && dst[index+1]<0) || a[index]==w[index]) //后面一组是减少的 或者较小的那个数不能增大了 那么直接index+1减少{a[index+1]--;} else{a[index]++; //后面一组也是增大 那么当前第一个数 增大}} else{if(dst[index+1]<0) //后面一组是减少的 那么直接index+1减少a[index+1]--;else{if(dst[index-1]<0) //前面一组是减少的{if(a[index]<w[index]) //优先选择index++a[index]++;else //前面一个数不能增大 那么只能后面的数减少a[index+1]--;} else //三组都是增大的{if(dst[index-1]<dst[index+1] || a[index]==w[index]) //前面那组 增大趋势更大a[index+1]--;else{a[index]++;}}}}} else //当前a[index] => a[index+1]是减少的{if(index==n-2) //如果这是最后两个数{if((index-1>=0 && dst[index-1]>0) || a[index+1]==w[index+1]) //如果前面一组是增大的 或者较小的那个数不能增大{a[index]--;} else{a[index+1]++;//那么直接最后那个数减少}}else if(index==0) //第一、二个数{if((index+1<=n-2 && dst[index+1]<0 ) || a[index+1]==w[index+1]) //后面一组是减少的 或者较小的那个数不能增大了{a[index]--;//那么只能较大的那个数减少} else{a[index+1]++;}} else{if(index+1<=n-2 && dst[index+1]>0) //后面一组是增大的{if(a[index+1]<w[index+1])a[index+1]++; //较小的那个数增大elsea[index]--;}else{if(index-1>=0 && dst[index-1]>0) //前面一组是增大的{a[index]--;//直接较大的数减少} else //三组都是减少的 那么需要权衡 前后两组dst{if(dst[index-1]>dst[index+1] || a[index+1]==w[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;}
验证代码：
int main()
{vector<int> a={12,4,7,9,1};vector<int> b={15,15,15,15,15};cout<<solve(5,4,a,b)<<endl;}