房屋拆分问题:
例如,将面积为200的房间分拆为面积为80、70和50的三个车间,第一次将房屋分拆为面积120和80的两个房间,花费200,第二次将面积为120的房间分拆为面积为70和50的两个房间,花费120,总花费为320。如果采用另一种方案,第一次将面积200的房屋分拆为150和50,花费200,第二次将面积为150的房间分拆为80和70的房间,花费150,则总花费为350。
第一行为一个整数n,表示所需的车间数量。第二行为n个正整数,以空格间隔,给出每个车间需要的面积。
n = 8
1 1 1 1 2 3 4 5
解题思路:
从小到大排列数组;
两个最小值相加,得到c,删除这两个值,将c放入数组中,重新排序。
代码演示:
PriorityQueue<Long> arr = new PriorityQueue<>(); //数组long total = 0;while (arr.size() > 0) {long a = arr.poll();long b = arr.poll();long c = a + c;total += c;arr.add(c);}
PriorityQueue
PriorityQueue用法:
arr.add();//入队
Long peek = arr.peek();//查看队首元素,不删除
Long poll = arr.poll();//出队,删除元素
arr.isEmpty();//判空
arr.size();//元素个数
arr.clear();//清空队列