集训心得——贪心算法

53 阅读 0 评论 35 点赞

我是靠谱客的博主大力黑猫，最近开发中收集的这篇文章主要介绍集训心得——贪心算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

所谓贪心，就是在有限制的情况下去最大程度的达到我们的目的。

以下列举几个贪心的典型例题：

1.排队问题

问题描述：n个人到r个水龙头接水，装满水桶的时间分别未t1,t2,t3……接水的时间是互不相等的整数，怎样安排可以使每个人的等待时间和最小？

问题解决：对n个人的打水时间从大到小排序即可，因为排队越靠前被计算的次数就越多，这样就可以达到打水时间最短的目的。

输入：

第一行：输入总共人数。

第二行：输入每个人的接水时间，并用空格隔开。

输出：

一个整数，最小的等待时间。

#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;

int main()
{
	int n,t[1001]; //定义总人数，和储存每个人接水时间的数组
	double waitingtime = 0;  //定义等待时间
	cin >> n; //输入总人数
	for(int i = 0;i < n;i++)  //输入每个人的接水时间
		cin >> t[i];
	sort(t,t+n); //对每个人的接水时间排序
	for(int i = 0;i < n;i++)  //计算总共的等待时间
	{
		for(int j = 0;j < i;j++)
			waitingtime += t[j];
	}
	cout << waitingtime; //输出最小的等待时间
	return 0;
}

2.最优装载问题

问题描述：现有n个物体，第i个物体的重量为Wi。在总重量不超过C的前提下选择尽量多的物体。

问题解决：该问题提出需要尽可能多的装物体，我们只关心物体的数量，选择装轻的物体可以使我们装更多。因此对物体的重量进行排序后，依次选择物体，直至装不下了。（考虑装不满的情况）

3.部分背包问题

问题描述：该问题与最优装载问题相似。有n个物体，第i个物体的重量为Wi，价值为Vi。在总重量不超过C的情况下让总价值尽可能的高。物体可以只取走一部分。

问题解决：该问题关心的是价值，我们需要得到更高的价值，因此将物体的价值从高到低排序，由于可以部分拿，因此当重量和正好为C时即可。（此处应该要注意：背包装不满的情况。）

4.乘船问题

问题描述：有n个人，第i个人重量为Wi。每艘船的最大载重量为C，且最多只能坐两个人。用最少的船能够承载所有人。

问题解决：遇到这个问题，应该会想到要最轻的和最重的做一艘船并依次类推，若最轻和最重的坐一艘船仍然超重，那么最重的那个人就单独坐一艘船，以此道理类推即可。

下面给出一个例题：

题目描述

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入格式

共 n+2n+2 行：

第一行包括一个整数 ww，为每组纪念品价格之和的上上限。

第二行为一个整数 nn，表示购来的纪念品的总件数 GG。

第 3sim n+23∼n+2 行每行包含一个正整数 P_iPi 表示所对应纪念品的价格。

输出格式

一个整数，即最少的分组数目。

代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
struct m{
	int p;
};
int cmp(m m1,m m2)
{
	return m1.p < m2.p;
}
int main()
{
	int w,n;
	cin >> w >> n;
	m x[30005];
	for(int i = 0;i < n;i++)
		cin >> x[i].p;
	sort(&x[0],&x[0] + n,cmp); //从小到大排序
	int sum = 0; //定义总数
	int low = 0,high = n-1;
    while(low <= high)
    {
        if(x[low].p + x[high].p <= w)
        {
            low++;
        	high--;
        	sum++;
        }
        else
        {
            high--;
            sum++;
        }
    }
	cout << sum;
	return 0;
}

5.区间类

问题描述：数轴上有n个开区间（ai，bi）。尽可能选择多个区间，使区间两两没有公共点。

问题解决：首先将区间右端点进行排序（右端点越小，留出的空间越多）。并使所取的第i个区间的右端点小于等于第i+区间的左端点。因为贪心策略，一定要选第一个区间，再根据上述条件继续选择。

#include <iostream>
#include <algorithm>
using namespace std;
struct m{
	int a;
	int b;
};
int cmp(m m1, m m2) {
	return m1.b<m2.b;
}
int main()
{
	int n;
	m c[1000005];
	cin >> n;
	for(int i = 0;i < n;i++)
		cin >> c[i].a >> c[i].b;
	sort(&c[0], &c[0]+n, cmp); //对右端点从小到大排序
	int max = 1; //代表已经选取了第一段
	for(int i = 0;i < n;i++)
	{
		for(int j = i;j < n;j++)
		{
			if(c[i].b <= c[j].a) //选取左端点大于等于该区间的右端点的线段为下一区间
			{
				max++;
				i = j - 1;
				break;
			}
			else
				continue;
		}
	}
	cout << max;
	return 0;
}

以上就是贪心算法的部分总结~