贪心的过程要么是最大要么是最小，堆可以很好的满足这个要求。
问题1：一块金条切成两半，是需要花费和长度数值一样的铜板的。比如
长度为20的 金条，不管切成长度多大的两半，都要花费20个铜
板。一群人想整分整块金 条，怎么分最省铜板？
例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为
10+20+30=60. 金条要分成10,20,30三个部分。 如果， 先把长
度60的金条分成10和50，花费60 再把长度50的金条分成20和30，
花费50 一共花费110铜板。
但是如果， 先把长度60的金条分成30和30，花费60 再把长度30
金条分成10和20，花费30 一共花费90铜板。
输入一个数组，返回分割的最小代价。
import java.util.Comparator;
import java.util.PriorityQueue;
public class ddd {
public int lessMoney(int[] array){
PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
for(int i = 0; i < array.length; i++)
minHeap.add(array[i]);
while (minHeap.size() > 1){
int one = minHeap.poll();
int two = minHeap.poll();
minHeap.add(one + two);
}
return minHeap.poll();
}
public static void main(String[] args) {
int[] arr = {10, 20, 30, 10};
System.out.println(new ddd().lessMoney(arr));
}
}
问题2：输入： 参数1，正数数组costs 参数2，正数数组profits 参数3，
正数k 参数4，正数m
costs[i]表示i号项目的花费 profits[i]表示i号项目在扣除花
费之后还能挣到的钱(利润) k表示你不能并行、只能串行的最多
做k个项目 m表示你初始的资金
说明：你每做完一个项目，马上获得的收益，可以支持你去做下
一个 项目。
输出： 你最后获得的最大钱数。
import java.util.Comparator;
import java.util.PriorityQueue;
public class moreProfile {
private class Node{
public int c;
public int p;
public Node(int c, int p){
this.c = c;
this.p = p;
}
}
public int moreProfile(int[] costs, int[] profits, int k, int m){
PriorityQueue<Node> minCost = new PriorityQueue<>(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.c - o2.c;
}
});
PriorityQueue<Node> maxProfits = new PriorityQueue<>(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o2.p - o1.p;
}
});
Node[] nodes = new Node[costs.length];
for(int i = 0; i < nodes.length; i++)
nodes[i] = new Node(costs[i], profits[i]);
for(int i = 0; i < nodes.length; i++)
minCost.add(nodes[i]);
for(int i = 0; i < nodes.length; i++){
while (!minCost.isEmpty() && minCost.peek().c <= m){
maxProfits.add(minCost.poll());
}
if(maxProfits.isEmpty())
return m;
m += maxProfits.poll().p;
}
return m;
}
public static void main(String[] args) {
int[] costs = {10, 20, 5, 8, 100};
int[] profits = {5, 9, 1, 2, 30};
int k = 5, m = 30;
System.out.println(new moreProfile().moreProfile(costs, profits, k, m));
}
}
问题3：
给定一个字符串类型的数组strs，找到一种拼接方式，使得把所
有字 符串拼起来之后形成的字符串具有最低的字典序。
import java.util.Comparator;
import java.util.PriorityQueue;
public class Str {
public String bestStr(String[] str){
PriorityQueue<String> minHeap = new PriorityQueue<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
String one = o1 + o2;
String two = o2 + o1;
return one.compareTo(two);
}
});
for(int i = 0; i < str.length; i++)
minHeap.add(str[i]);
String res = "";
while (!minHeap.isEmpty())
res += minHeap.poll();
return res;
}
public static void main(String[] args) {
String[] str = {"ba", "b" };
System.out.println(new Str().bestStr(str));
}
}
问题4：一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目
的宣讲。 给你每一个项目开始的时间和结束的时间(给你一个数
组，里面 是一个个具体的项目)，你来安排宣讲的日程，要求会
议室进行 的宣讲的场次最多。返回这个最多的宣讲场次。
import java.util.Comparator;
import java.util.PriorityQueue;
public class BestArrange {
private class Program{
public int start;
public int end;
public Program(int start, int end){
this.start = start;
this.end = end;
}
}
public int BestArrange(Program[] pro, int start){
PriorityQueue<Program> minHeap = new PriorityQueue<>(new Comparator<Program>() {
@Override
public int compare(Program o1, Program o2) {
return o1.end - o2.end;
}
});
for(int i = 0; i < pro.length; i++){
minHeap.add(pro[i]);
}
int res = 0;
for(int i = 0; i < pro.length; i++){
if(start <= minHeap.peek().end){
res++;
start = minHeap.poll().end;
}
}
return res;
}
}
