[数据结构与算法]【贪心算法】手办合并

题目描述

分析
首先要明白5点

1. 想要保证距离最短每个手办必须只朝一个方向（左/右）移动n米（总不可能先左后右这样折返，得不偿失）
2. 每个手办的移动操作可以分解成更细小的按照一米一米的移动操作，比如一个手办向右移动4米就可以分解为四个向右移动一米的操作
3. 在2前提下会出现手办移动后和另一个手办位置重叠的情况，这个时候重叠的两个手办就可以合并，新的权值就是两个手办权值之和
4. 任意更改手办之间的移动顺序不会影响结果。先移动手办1和先移手办3对结果是没有任何影响的，甚至先讲手办1移动1m再将手办3移动2m再将手办1移动3m也是不会对结果造成影响的
5. 总移动次数永远不变。假设有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<n;i++){
            handDo[i]=scanner.nextInt();
        }
        int l=0,r=n-1;
        int work=0;//做功
        while (l!=r){//l!=r说明还没合并成一堆，需要继续合并
            if(handDo[l]<handDo[r]){//左右两个哪个权值小就合并哪个
                handDo[l+1]+=handDo[l];//更新权值
                work+=handDo[l];
                l++;
            }else {
                handDo[r-1]+=handDo[r];//更新权值
                work+=handDo[r];
                r--;
            }
        }
        System.out.println(work);
    }
}

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系