题目链接

http://poj.org/problem?id=3253

题目描述

大意：切长度为a的木条的花费是a，给定最终切好的n段各自的长度，问由原来的一根木条(长度为n段长度和)以最终总花费最小的方法切这n-1下，输出最小花费。(切的中间过程产生的子段不同，所以花费会不同)

例子：
输入：
3
8 5 8
输出：
34
提示：
（8+5）+（13+8）=34

题解

• 过程反着想，就是合并子段的过程。
• 数据结构：两个单调递增队列。
  • 第一个放进原始的n段的长度。
  • 第二个用来放合并后的段的长度。
  • 每次贪心地选择两个队列头最小的两个段合并。合并后放入队列2头部，可以知道队列2也是单调递增的。

代码

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        LinkedList<Integer> q=new LinkedList<Integer>();
        while(n--!=0) {
            q.addLast(in.nextInt());
        }
        int cost=getMinCost(q);
        System.out.println(cost);
    }
    
    public static int getMinCost(LinkedList<Integer> q) {
        q.sort(null);
        int n=q.size()-1;//切(合并)的次数
        LinkedList<Integer> sumQue=new LinkedList<>();
        int sum=0;
        while(n--!=0) {
            int tempSum=0;
            int cnt=2;
            while(cnt--!=0) {
                if(sumQue.isEmpty()||(!sumQue.isEmpty()&&!q.isEmpty()&&q.peekFirst()<=sumQue.peekFirst())) {
                    tempSum+=q.pollFirst();
                }
                else {
                    tempSum+=sumQue.pollFirst();
                }
            }
            sum+=tempSum;
            sumQue.addFirst(tempSum);
        }
        return sum;
    }
}