贪心法(——模板习题与总结)
摘要
本文主要讲解贪心法的基本思想和实现,怎么运用贪心法,着重讲解在编程竞赛中的一些典型应用。
什么是贪心法?
在编程竞赛中的典型应用有哪些?
例题解析
什么是贪心法?
贪心法本质上讲不是一种真正的算法,而是一种思想,就是解决问题的时候遵循着某种规则,不断贪心地选取当前最优策略,以达到结果最优的目的。比如硬币问题,给出1元、5元、10元、50元、100元的硬币各a、b、c、d、e个,问用这些硬币来支付A元,最少需要多少枚硬币?
很容易想到先用面额大的钱,依次往小即可。这就是贪心法的典型应用,只顾眼前的利益最大化,从而达到总体最优的效果。
在编程竞赛中的典型应用有哪些?
硬币问题,给出硬币的面额和个数,给出需要支付的钱数A,问至少、至多需要多少个硬币?比如HDU 3348 coins
区间问题,给出区间的个数和各个区间的起始和终止,问不能交叉的选取,最多能选取多少个区间?比如HDu 2037 今年暑假不AC
字典序最小问题,给出一个字符串,每次只能从头或者尾取一个字符组成另一个字符串,问字典序最小的字符串是哪个?比如POJ 3617 Best Cow Line
点覆盖问题,给出一个点能够覆盖的范围r和点数以及每个点的位置,问最少需要多少个点使得所有的点都被覆盖? 比如POJ 3069 Saruman’s Army
哈夫曼编码问题,给出总的木板长度,需要分割的n个木块及长度,问将这根木板分割成n段的最小代价是多少,其中切割的代价等于被切木板的长度,比如将长度为13的木板切成8和5,所花费的代价是13。比如POJ 3253 Fence Repair
例题解析
HDU 3348 coins 问至少和至多需要多少个硬币,至少容易求,直接贪心先选取面额大的硬币即可,关键是怎么求最多需要多少硬币,有人想到还使用贪心,先选取面额小的硬币,这样是有漏洞的,优先将小的硬币选完之后,可能造成无法凑成A。
这里采用一种反向思维的解法,要想给出的硬币最多,那么手中剩下的硬币就得最少,这样就可以按照之前的方法解题了。只不过要凑的钱数变成了sum-A,计算出的是凑完手中钱最少需要多少个硬币,再用总的硬币数减去它,就可以的到答案了。参考代码如下:
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int v[5] = {1, 5, 10, 50, 100}; 6 7 int main() 8 { 9 int T; 10 int A, a[5]; 11 scanf("%d", &T); 12 while(T--) { 13 scanf("%d%d%d%d%d%d", &A, &a[0], &a[1], &a[2], &a[3], &a[4]); 14 int mina = 0; 15 int p1 = A; 16 for(int i = 4; i >= 0; i--) { 17 int t = min(p1 / v[i], a[i]); 18 p1 -= t * v[i]; 19 mina += t; 20 } 21 22 int maxa = 0; 23 int sum = a[0] + 5 * a[1] + 10 * a[2] + 50 * a[3] + 100 * a[4]; 24 int p2 = sum - A; 25 for(int i = 4; i >= 0; i--) { 26 int t = min(p2 / v[i], a[i]); 27 p2 -= t * v[i]; 28 maxa += t; 29 } 30 maxa = a[0] + a[1] + a[2] + a[3] + a[4] - maxa; 31 32 if(p1 != 0 || p2 != 0) 33 printf("-1 -1\n"); 34 else 35 printf("%d %d\n", mina, maxa); 36 } 37 return 0; 38 }
HDu 2037 今年暑假不AC 典型的区间调度问题,先将区间按照结束的早的优先级高的规则排序,然后每次选取结束时间最早的区间。用到了结构体排序,注意迭代的过程。
参考代码如下:
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int maxn = 110; 6 struct Node { 7 int s, e; 8 }node[maxn]; 9 bool cmp(Node a, Node b) { 10 if(a.e == b.e) 11 return a.s < b.s; 12 return a.e < b.e; 13 } 14 int main() 15 { 16 int n; 17 while(scanf("%d", &n) == 1 && n) { 18 for(int i = 0; i < n; i++) { 19 scanf("%d%d", &node[i].s, &node[i].e); 20 } 21 sort(node, node + n, cmp); 22 23 int ans = 0, t = 0; 24 for(int i = 0; i < n; i++) { 25 if(t <= node[i].s){ 26 ans++; 27 t = node[i].e; 28 } 29 } 30 printf("%d\n", ans); 31 } 32 return 0; 33 }
POJ 3617 Best Cow Line 很容易想到贪心的规则是每次从头或者尾选取较小的字符,不过需要注意的是如果两个字符相等,就需要比较后面的,换句换说就要比较一个串的正和反哪个字典序小,从而得出结论。实现较为巧妙,参考代码:
1 /* 2 给出一个字符串,问每次只能从头或者尾取一个字符,组成最小字典序的字符串 3 每次比较从左起和从右起的字符串,比较出就输出 4 */ 5 #include <cstdio> 6 7 const int maxn = 101000; 8 char s[maxn], rs[maxn]; 9 10 int main() 11 { 12 int n, cnt = 0; 13 while (scanf("%d", &n) != EOF) { 14 for (int i = 0; i < n; i++) { 15 scanf(" %c", &s[i]); 16 } 17 s[n] = '\0'; 18 //puts(s); 19 20 int a = 0, b = n - 1; 21 while (a <= b) { 22 bool left = false; 23 //比较从左起和从右起的字符串 24 for (int i = 0; a + i <= b; i++) { 25 if (s[a + i] < s[b - i]) { 26 left = true; 27 break; 28 } else if (s[a + i] > s[b - i]) { 29 left = false; 30 break; 31 } 32 } 33 34 if (left) putchar(s[a++]); 35 else putchar(s[b--]); 36 cnt++; 37 if(cnt == 80){ 38 printf("\n"); 39 cnt = 0; 40 } 41 } 42 printf("\n"); 43 } 44 return 0; 45 }
POJ 3069 Saruman’s Army 典型的点覆盖问题,贪心的规则是保证能够覆盖最左边的点的情况下,尽量选取一个靠左点,然后跳过它能够覆盖的点,如此重复。代码如下:
1 /* 2 给出一个灯能够照亮的范围r,给出n个点的位置,问至少需要安装多少个灯,使得每个点都在灯的范围内 3 使用贪心法,找到一个最左边的位置,加上r,跳过能够覆盖的所有点,找到第一个不能覆盖的点,作为灯, 4 然后再往右走r,跳过r内的点,计数,直到走完。 5 */ 6 #include <cstdio> 7 #include <algorithm> 8 using namespace std; 9 10 const int maxn = 1010; 11 12 int a[maxn]; 13 int main () 14 { 15 int r, n; 16 while (scanf("%d%d", &r, &n) == 2 && r + n != -2) { 17 for (int i = 0; i < n; i++) { 18 scanf("%d", &a[i]); 19 } 20 sort (a, a + n); 21 22 int i = 0, ans = 0; 23 while (i < n) { 24 int s = a[i++]; 25 while (i < n && s + r >= a[i]) 26 i++; 27 int p = a[i - 1]; 28 while (i < n && p + r >= a[i]) 29 i++; 30 31 ans++; 32 } 33 printf ("%d\n", ans); 34 } 35 return 0; 36 }
POJ 3253 Fence Repair 该题的解法作为计算法哈夫曼编码的算法而被熟知,使用了C++ STL 中的优先队列,实现起来非常简单。优先队列自定义优先级的两种方法如下:
1 #include <cstdio> 2 #include <queue> 3 using namespace std; 4 typedef long long LL; 5 priority_queue<int, vector<int>, greater<int> > pq; 6 int main() 7 { 8 int n; 9 while (scanf("%d", &n) != EOF) { 10 while(!pq.empty()) 11 pq.pop(); 12 13 int tmp; 14 for(int i = 0; i < n; i++) { 15 scanf("%d", &tmp); 16 pq.push(tmp); 17 } 18 19 LL ans = 0; 20 while(pq.size() > 1) { 21 int min1 = pq.top(); 22 pq.pop(); 23 int min2 = pq.top(); 24 pq.pop(); 25 26 ans += min1 + min2; 27 pq.push(min1 + min2); 28 } 29 printf("%lld\n", ans); 30 } 31 return 0; 32 }
1 #include <cstdio> 2 #include <queue> 3 using namespace std; 4 typedef long long ll; 5 struct cmp { 6 bool operator () (const int &a, const int &b) const { 7 return a > b; 8 } 9 }; 10 priority_queue<int, vector<int>, cmp> pq; 11 12 int main () 13 { 14 int n; 15 while (scanf("%d", &n) != EOF) { 16 while (!pq.empty()) 17 pq.pop(); 18 for (int i = 0; i < n; i++) { 19 int tmp; 20 scanf("%d", &tmp); 21 pq.push(tmp); 22 } 23 ll ans = 0; 24 while(pq.size() > 1) { 25 int min1 = pq.top(); 26 pq.pop(); 27 int min2 = pq.top(); 28 pq.pop(); 29 30 ans += min1 + min2; 31 pq.push(min1 + min2); 32 } 33 printf("%lld\n", ans); 34 } 35 return 0; 36 }
贪心法最大的特点就是和动态规划的相比只顾眼前的最优,熟悉动态规划的话,对贪心法会有更深层的理解,另外求解最短路中的prim算法和Dijkstra算法等都是运用了贪心法的思想。要学会并不难,关键是多动手实践。