贪心算法介绍

• 1. 贪心算法的解题套路
• 题目1：会议安排问题
• 题目2：哈夫曼编码问题

贪心问题，堆和排序是最常用的办法

• 思路
  按会议结束时间排序，依次取出会议结束时间最早的会议

#include
#include
using namespace std;

bool cmp(vector N1,vector N2)
{
	return N1[1] > N2[1];
}

int main()
{
	int count = 0;
	int endtime = 0;
	vector>   HY = { {11,13},{18,20} ,{12,15},{6,8},{14,17},{7,9},{7,10} };
	priority_queue, vector>, decltype(&cmp)>  que(cmp);
	for (int i = 0; i < HY.size(); i++)
	{
		que.push(HY[i]);
	}
	while (!que.empty())
	{
		vector cur_HY = que.top();
		que.pop();
		if (endtime < cur_HY[0])
		{
			count++;
			endtime = cur_HY[1];
		}
	}
	cout << count << endl;
	return 0;
}

• code

int main()
{
	priority_queue, greater> que;
	int cost = 0;
	vector Arr = { 1, 2, 6, 4, 8, 6, 10, 5, 45 };
	for (int i = 0; i < Arr.size(); i++)
	{
		que.push(Arr[i]);
	}
	while (que.size() > 1)
	{
		int N1 = que.top();
		que.pop();
		int N2 = que.top();
		que.pop();
		int S = N1 + N2;
		cost += S;
		que.push(S);
	}
	cout << cost << endl;
	return 0;
}

贪心策略题目，coding很简单，主要是思路