下面给出线性算法(O(n))和分治算法(O(n^2))其中分治算法的正确性显见而线性算法的正确性可由分治算法得出线性算法关键点当前堆数量可为负数步骤从左到右遍历数组若大于目标值则将多余数量转移给下一元素移动次数(最终结果)1若小于目标值则从下一元素支取所差数量(透支不影响结果)移动次数1若等于目标值跳过复杂度显然O(n)分治算法算法对于区间[lo,hi)若区间内元素小于2个返回0找到区间内元素最大值若最大值为目标值返回0遍历最大值左边元素找到还差多少记为left遍历最大值右边元素找到还差多少记为right将最大值元素值置为目标值记当前移动次数total0若left不为0则最大值元素的左边第一个元素值加上left.total若right不为0则最大值元素的右边第一个元素值加上righttotal分别对最大值元素左边区间和右边区间递归执行该算法total加上它们返回的值作为当前区间执行算法的返回值正确性该算法实际上就是实际寻找的过程正确性显然复杂度该算法与快排很类似都为找到轴点(这里是最大值)进行二分因此可类似快排构造最坏情况因此算法复杂度为O(n^2)但平均性能应该也为O(log n)类似快排若每次最大值都在中间则有递归式T(n) 2T(n/2) O(n)因此主定理解得O(log n)线性算法正确性证明算法正确性证明考虑分治算法得到的一个最优解证明线性算法得到的解与其等价(最少移动次数相同)记初始数组为A每次移动都可以用一个三元组(u,v,w)来刻画表示从A[u]取w转移到A[v]满足|u-v|1,w0由此由分治算法得到的解应该是一个操作序列其中集合元素为上述三元组满足每一次的操作都是合法的(不会出现透支)集合元素个数最少再将这个操作集合用图来建模图的节点代表堆(u,v,w)代表从u指向v的一条权重为w的有向边称上述最优解对应的图为最优图下面证明(注意下面所说的最优操作序列都是由分治算法得到)最优图不存在重边即若最优操作序列中存在(u,v,w)则不存在(u,v,w1)或者(v,u,w2)考虑分治算法的操作流程每次迭代都找到一个最大值并对最大值两边的区间(都不包含最大值)进行相同处理而每次迭代最多进行2次移动操作即最大值分别向左右两边移动一定数值而之后的迭代将不再与该最大值相关(因为后面的区间都不包含它)所以不会出现重边最优图的边去掉方向后每个连通分量对应的子图都为一条欧拉路径由(u,v,w)满足|u-v|1和不存在重边立即得到注意该图不一定连通这对应着分治算法中最大值为目标值的情况此时将不会存在移动即该节点不会有边与其相连改变最优图边的生成方式即等价于线性算法对最优图进行改变对于每条边(u,v,w)若uv则不变;若uv则去掉该边加上一条(v,u,-w)权重为负数此时节点序号从小到大遍历对于节点i和节点i1若不存在边(i,i1,w)则继续遍历下一节点;若存在w0则从当前节点i对应堆移动w到下一节点w0则节点i1对应堆向节点i对应堆移动-ww0则继续遍历下一节点经过上述操作每个节点值都将成为目标值满足要求同时由其步骤显然就是线性算法的运行步骤而最优图是由分治算法得到的因此由分治算法正确性即可得到线性算法的正确性monell太强了就是没留代码~虽然看不懂但看着很高级的样子给大家看看我的代码吧有注释版// 引入万能头文件包含所有常用标准库#includebits/stdc.h// 使用标准命名空间省去std::前缀usingnamespacestd;// 定义全局整型数组a下标范围0~10000inta[10001];// 程序入口主函数intmain(){// 定义循环变量i、数据个数n、移动步数s初始化为0、平均值临时变量pinti,n,s0,p;// 从控制台输入数字n表示一共有多少个数字cinn;// 循环i从1到n依次遍历每个数据for(i1;in;i){// 输入第i个数字存入数组a[i]cina[i];// 将当前输入的a[i]累加到p中p用来存储所有数的总和pa[i];}// 总和除以个数np现在变为所有数字的平均值p/n;// 再次循环遍历1~n每一个数组元素for(i1;in;i){// 判断当前数字不等于平均值说明需要调整if(a[i]!p){// 把当前数字与平均值的差值转移给下一个元素a[i1]a[i1](a[i]-p);// 操作次数1记录移动步数s;}}// 输出总操作步数scouts;}无注释版#includebits/stdc.husingnamespacestd;inta[10001];intmain(){inti,n,s0,p;cinn;for(i1;in;i){cina[i];pa[i];}p/n;for(i1;in;i){if(a[i]!p){a[i1]a[i1](a[i]-p);s;}}couts;}豆包神力OK,到此为止下课!