题目描述
分析
首先要明白5点
- 想要保证距离最短每个手办必须只朝一个方向（左/右）移动n米（总不可能先左后右这样折返，得不偿失）
- 每个手办的移动操作可以分解成更细小的按照一米一米的移动操作，比如一个手办向右移动4米就可以分解为四个向右移动一米的操作
- 在2前提下会出现手办移动后和另一个手办位置重叠的情况，这个时候重叠的两个手办就可以合并，新的权值就是两个手办权值之和
- 任意更改手办之间的移动顺序不会影响结果。先移动手办1和先移手办3对结果是没有任何影响的，甚至先讲手办1移动1m再将手办3移动2m再将手办1移动3m也是不会对结果造成影响的
- 总移动次数永远不变。假设有10个手办一排，你会发现不管是以哪个位置为中心移动，最后的总移动次数都是1+2+3+…+9=45次（注意这里是指45次一米的移动操作，详见2）。参考3，由于手办可以合并成一个手办，这样此实际移动次数并不需要45次，而是只需要9次（想一想为什么），接下来题目中我们也是按照后者更少的移动方式来进行。
接下来我们假设一排有10个手办
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ <-手办
1 2 5 3 2 4 3 4 2 2 <-权值
根据结论4，我们每次可以将问题简化为：
有一堆手办，每次可以将最左的手办向右移动或者将最右的手办向左移动，问最终手办合成一堆后所做的功最少是多少？
接下来我们就解决这个等价问题即可。
根据5可知，在进行9次操作后，我们的手办就合并成一堆了。那我们是不是只要找到做功最小的9次操作就可以了。
首先我们放眼望去，最小的操作是哪个？
很显然是将第一个手办和第二个手办合并，只需要做1w的功。（这个是所有操作里做功最小的操作）
后并后就是这样
■ ■ ■ ■ ■ ■ ■ ■ ■ <-手办
3 5 3 2 4 3 4 2 2 <-权值
现在最小的呢？
其实也很显然，是最右边两个手办合并，最终做了2w的功。（这个是所有操作里做功第二小的操作）
为什么？
我们知道手办是越合并越大的，到后面合并做的功只会变大不会变少，所以左右两边的操作肯定有一个是当前最小的。所以当前最优的操作其实就是全局最优的。符合贪心准则里的：局部最优推全局最优。所以这个贪心方法是正确的。也就是当前左右两个手办哪个权值小我就合并哪一边。
代码实现
import java.util.Scanner;
public class Main2
{
public static void main(String[] args) {
Scanner scanner =new Scanner(System.in);
int n=scanner.nextInt();//有n个手办
int[] handDo=new int[n];//存手办权值
for(int i=0;i
handDo[i]=scanner.nextInt();
}
int l=0,r=n-1;
int work=0;//做功
while (l!=r){//l!=r说明还没合并成一堆，需要继续合并
if(handDo[l]//左右两个哪个权值小就合并哪个
handDo[l+1]+=handDo[l];//更新权值
work+=handDo[l];
l++;
}else {
handDo[r-1]+=handDo[r];//更新权值
work+=handDo[r];
r--;
}
}
System.out.println(work);
}
}
