贪心算法
贪心的过程要么是最大要么是最小，堆可以很好的满足这个要求。 问题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; } }
