算法学习笔记之贪心算法

导引（硕鼠的交易）

硕鼠准备了M磅猫粮与看守仓库的猫交易奶酪。

仓库有N个房间，第i个房间有 J[i] 磅奶酪并需要 F[i] 磅猫粮交换，硕鼠可以按比例来交换，不必交换所有的奶酪

计算硕鼠最多能得到多少磅奶酪。

输入M和N表示猫粮数量和房间数量，随后输入N个房间，每个房间包括奶酪数和猫粮数

Input

 5 37 24 35 2-1 -1

Output

 13.333

解法：计算每个房间的奶酪与猫粮之比，比值越大硕鼠收益越高，将所有比值从大到小排序，最后选择比值大的即可。

例1（田忌赛马）

问题描述：田忌与齐王赛马，每匹马的速度不同。

目标：赢得最多的比赛。

策略：利用田忌的最弱的马去对齐王的最强的马，反之亦然。

不要固定认为是将田忌第一强的马与齐王第二强的马进行比较，因为可能田忌第一强的马比齐王第一强的马更强

经典贪心（事件序列问题）

命题：至少存在一个最长的事件序列，包含最早结束的事件

采用反证法证明：假设有一个最长的事件序列bcdef，不包含最早结束的事件a，显然a在b之前结束，那么事件序列acdef依旧是最短事件序列。

显然，选中最早结束的事件对最长的事件序列无影响。

那么，我们可以选中最早结束的事件0，然后再选中发生时刻大于等于3，且结束时刻最小的事件；

继续选中事件1，然后再选中发生时刻大于等于4，且结束时刻最小的事件；

继续选中事件5，然后再选中发生时刻大于等于10，且结束时刻最小的事件；

继续选中事件8，然后再选中发生时刻大于等于15，且结束时刻最小的事件；

继续选中事件10，然后发现没有可选事件了，最长事件序列为0,1,5,8,10

贪心思路：先把所有事件按结束时刻从大到小排序，随后每次选择一个最早结束且和之前不冲突的事件

例2（搬桌子）

一层楼的布局如上，现在需要将一些桌子从一个房间搬到另一个房间。无论距离远近，每趟搬运都需要十分钟。

当你从房间 i 搬桌子到房间 j 时，房间 i 到房间 j 的走廊被占用，也就是同一时间的走廊是互斥的。

现在需要计算完成所有搬运任务最少需要多长时间。

输出包含T组用例。首先输入一个正整数N，表示需要搬运的桌子数，接下来N行，每行包含2个正整数a和b，表示需要将桌子从a房间搬到b房间

输出为每组用例搬运任务需要的最少时间。

思路：记录每段区间的走廊被占用的次数，重合的次数就是需要搬运的次数

 #include<iostream>​using namespace std;​int t, i, j, N, P[200]; int s, d, temp, k, MAX;​int main(){cin >> t;for(i = 0; i < t; i++){// 初始化 for(j = 0; j < 200; j++){P[j] = 0;}cin >> N;for(j = 0; j < N; j++){cin >> s >> d;s = (s-1)/2;d = (d-1)/2;if(s > d){swap(s, d);}for(k = s; k <= d; k++){P[k]++;}}MAX = -1;for(j = 0; j < 200; j++){MAX = max(MAX, P[j]);}cout << MAX*10 << endl;}return 0;}

例3（删数问题）

思路：显然高位越小越好。每次比较相邻两数，若左边比右边大则删去左边的数，否则继续比较后面的数。

例4（青蛙的邻居）

输入t组样例，每组样例先输入n个湖泊，每个青蛙呆在不同湖泊里面，然后输入n青蛙的邻居个数，问能否根据这些数据构成一个图。

问题本质：可图性判断

1、度序列：若把图G所有顶点的度数排成一个序列S，则称S为图G的度序列。

2、序列是可图的：一个非负整数组成的有限序列如果是某个无向图的度序列，则称该序列是可图的。

算法：Havel-Hakimi定理

由非负整数组成的非增序列S：d1 , d2, ... dn(n >= 2, d1 >= 1)是可图的，当且仅当序列S1：d2-1, d3-1, ..., dd1+1-1, dd1+2, ... ,dn是可图的。

其中，序列S1中有n-1个非负整数，S序列中d1后的前d1个度数(即d2 ~ dd1+1)减 1 后构成S1中的前d1个数。

通俗理解：

假设有一群人的邻居数为递增序列 5 4 4 3 2 1 1，若该序列成立，则第一个人有5个邻居，假设第一个人的五个邻居分别是2,3,4,5,6

当第一个人搬走了，剩下的人邻居个数为 3 3 2 1 0 1；排序后为为3 3 2 1 1 0

当第二个人搬走了，剩下的人邻居个数为 2 1 0 1 0；排序后为为2 1 1 0 0

当第三个人搬走了，剩下的人邻居个数为 0 0 0 0，此时该序列成立。

特别说明：若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！！

sort函数的使用

头文件

 #include<algorithm>

函数用法

sort(首地址，尾地址+1，cmp函数);

当不传入cmp函数时，默认递增

例：

 struct node{int a;double b;}arr[100];// 要求先按a升序，若a相等则按b降序bool cmp(node x, node y){if(x.a != y.a){return x.a < y.a;}return x.b > y.b;}