有n个箱子,第i个箱子一开始有个球,你可以进行最多k次操作,每次操作可以从一个箱子拿走一个球或者放入一个球。第i个箱子最多能装个球,装满了之后不能再往这个箱子里面放球。如果一个箱子为空,就不能从里面拿球。
设相邻箱子的球的数量的差的平方中的最大值为x,求进行最多k次操作之后x最小可以是多少。
5,4,[12,4,7,9,1],[15,15,15,15,15]
36
往第2个箱子放2个球,往第4个箱子放2个球得到[12,6,7,9,3],此时相邻箱子的球数差值为[-6,1,2,-6],平方后为[36,1,4,36],其中最大值为36
,
int solve(int n, int k, vector<int>& a, vector<int>& w) { for(int i=0;i<k;i++) //总共需要调整k次 { //首先计算出当前相邻差值最大的index vector<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(a[index]==w[index])//如果较小的那个数无法增大 那么直接较大的数减少 { a[index+1]--; continue; } if(index==n-2) //如果这是最后两个数 0=>n-1 dst[n-2]=a[n-1]-a[n-2] { if(index-1>=0 && dst[index-1]<0) //如果前面一组是减少的 { a[index]++; } else { a[index+1]--;//那么直接最后那个数减少 } } else if(index==0) //第一、二个数 { if(index+1<=n-2 && dst[index+1]<0) //后面一组是减少的 { a[index+1]--; } else { a[index]++; //后面一组也是增大 那么当前第一个数 增大 } } else { if(dst[index+1]<0) //后面一组是减少的 那么直接index+1减少 a[index+1]--; else { if(dst[index-1]<0) //前面一组是减少的 { a[index]++; } else //三组都是增大的 { if(dst[index-1]<dst[index+1]) //前面那组 增大趋势更大 a[index+1]--; else { a[index]++; } } } } } else //当前a[index] => a[index+1]是减少的 { if(a[index+1]==w[index+1]) //较小的那个数不能增大 { a[index]--; continue; } if(index==n-2) //如果这是最后两个数 { if(index-1>=0 && dst[index-1]>0) //如果前面一组是增大的 { a[index]--; } else { a[index+1]++;//那么直接最后那个数减少 } } else if(index==0) //第一、二个数 { if(index+1<=n-2 && 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 //三组都是减少的 那么需要权衡 前后两组dst { if(dst[index-1]>dst[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; }