贪心算法

贪心的过程要么是最大要么是最小，堆可以很好的满足这个要求。

问题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;
    }
}