贪心问题

定义:

1. 给定一个问题, 将问题的数据按照某个指标排序
2. 执行优先级由大到小执行

例题: 给定一个字符串集合, 将所有字符串拼接起来, 返回字典序最小的字符串
- 字典序: 两个字符串从头开始比, 相等下移, 不相等小的字典序小
思路:
- 贪心思路1 (错误: 例: “ba” 和 “b”组成集合):
  1. 对字符串集合按照字典序由小到大排序
  2. 从头开始拼接直到拼接完成返回
- 贪心思路2 (正确):
  1. 将比较规则由比较两个字符串修改为两个字符串按照字符串相加的方法得到两个新字符串后进行比较, 然后排序
  2. 从头开始拼接直到拼接完成返回

正确的代码

public static string LowestString(params string[] strs)
{
    Array.Sort(strs, (left, right) =>
    {
        string s1 = left + right;
        string s2 = right + left;
        return String.Compare(s1, s2, StringComparison.Ordinal);
    });
    StringBuilder sb = new StringBuilder();
    foreach (string str in strs)
    {
        sb.Append(str);
    }
    return sb.ToString();
}

贪心正确的前提:
- 排序必须具有传递性(很难证明)
使用:
- 如果好证明, 可以尝试证明
- 不好证明, 构建多个贪心算法, 使用对数器验证
- 如果对数器验证通过, 我们就可以认为这个贪心算法正确
例题: 一块金条切成两半, 是需要花费和长度数值一样的铜板的. 比如长度为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铜板.
输入一个数组, 返回分割的最小代价.

代码:

public static int getMinCost(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return 0;
    }
    PriorityQueue<Integer> queue = new PriorityQueue<>(){
        @Override
        public Comparator<? super Integer> comparator() {
            return (Comparator<Integer>) (o1, o2) -> o2.compareTo(o1);
        }
    };
    for (int item : arr) {
        queue.add(item);
    }
    int res = 0;
    while (queue.size() != 1) {
        int sum = queue.poll() + queue.poll();
        res += sum;
        queue.add(sum);
    }
    return res;
}

例题: 给定两个大小相同的数组A, B, 对于索引i, A[i]做这个项目花费的资金, B[i]是这个项目的纯利润, 给定一笔启动资金w, 求获得的收益最大是多少(一次只能做1个项目, 最多做k个项目)?
思路:
1. 将成本和利润封装称pair, 根据成本由小到大添加进一个优先级队列里.
2. 不断访问这个优先级队列, 当成本小于钱数, 把pair弹出, 按照利润由大到小放进另一个优先级队列里.
3. 每次访问都去第二个队列的队头, 增加完利润, 重复上述步骤.

代码:

int get_max_money(int k, int W, vector<int>& Profits, vector<int>& Capital)
{
	if (Capital.empty() || Capital.size() != Profits.size() || Profits.empty())
	{
		return 0;
	}
	const auto CapitalCom = [](const pair<int, int>& left, const pair<int, int>& right) -> bool {return left.first > right.first; };
	const auto ProfitCom = [](const pair<int, int>& left, const pair<int, int>& right) -> bool {return left.second < right.second; };
	priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(CapitalCom)> pq_cost(CapitalCom);
	priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(ProfitCom)> pq_profit(ProfitCom);
	for (int i = 0; i < Capital.size(); ++i)
	{
		pq_cost.push(make_pair(Capital[i], Profits[i]));
	}
	for (int i = 0; i < k; ++i)
	{
		while (!pq_cost.empty())
		{
			const auto [x, y] = pq_cost.top();
			if (x <= W)
			{
				pq_cost.pop();
				pq_profit.push(make_pair(x, y));
			}
			else
			{
				break;
			}
		}
		if (pq_profit.empty())
		{
			break;
		}
		const auto [x, y] = pq_profit.top();
		W += y;
		pq_profit.pop();
	}
	return W;
}

例题: 一些项目要占用一个会议室宣讲, 会议室不能同时容纳两个项目的宣讲. 给你每一个项目的开始的时间和结束的时间(给你一个数组, 里面是一个个具体的项目), 你来安排宣讲的日程, 要求会议室进行的宣讲的场次最多. 返回这个最多的宣讲场次.
思路:
- 按照谁开始的时间早, 谁先用(错误)
- 按照谁持续的时间短, 谁先用(错误)
- 按照谁结束的时间早, 谁先用(正确)

代码:

type Program struct {
	Begin int
	End int
}

type Programs []Program

func (programs Programs) Less(i, j int) bool {
	return programs[i].End < programs[j].End
}

func (programs Programs) Len() int {
	return len(programs)
}

func (programs Programs) Swap(i, j int) {
	programs[i], programs[j] = programs[j], programs[i]
}

func bestArrange(programs Programs, start int) int {
	if programs == nil || len(programs) <= 0 {
		return 0
	}
	sort.Sort(programs)
	result := 0
	for i := 0; i < len(programs); i++ {
		if start <= programs[i].Begin {
			result++
			start = programs[i].End
		}
	}
	return result
}