[关闭]
@Dmaxiya 2020-12-12T15:43:12.000000Z 字数 8104 阅读 1283

贪心练习题解

Hello_World


贪心

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。

以上复制自百度百科,详细内容可以点链接查看,由于贪心就是在每个子问题中尽可能地获得最大利益,不能说是一种算法,应该是一种解题思维,贪心经常和其他算法一起考察。
贪心的难点在于证明贪心思路的正确性,有些是显而易见的,而有些是需要一番推导的,这需要大量做题来熟悉。
今后的题解只说思路,不会具体介绍代码的每一步在做什么。

2 月 5 日 贪心练习题解

A. Doing Homework again

题意

要在 天内做完 套练习,每套练习都有一个分值和截止日期 ,他完成每套练习都需要一天时间,如果第 份练习完成的时间超过截止日期,则会被扣 分,问他最少会被扣多少分。

数据范围

题解

可以知道一定是分数越高的练习越早安排日期来做,但是不一定是第一天做,如果分数高但是截止日期比较靠后,则会占用其他练习的截止日期,我们可以将分数高的题目先安排,安排在最靠近这个练习截止日期的、没有被安排做作业的那一天来做,如果没有这样的日期可以安排了,就不做这一份作业,等着扣分了。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  19. #define LL long long
  20. const int maxn = 1000 + 100;
  21. struct Node {
  22. int day;
  23. int score;
  24. };
  25. bool operator<(const Node &a, const Node &b) {
  26. if(a.score == b.score) {
  27. return a.day > b.day;
  28. }
  29. return a.score > b.score;
  30. }
  31. int T, n, ans;
  32. Node node[maxn];
  33. bool vis[maxn];
  34. int main() {
  35. #ifdef LOCAL
  36. freopen("test.txt", "r", stdin);
  37. // freopen("out.txt", "w", stdout);
  38. #endif // LOCAL
  39. ios::sync_with_stdio(false);
  40. scanf("%d", &T);
  41. while(T--) {
  42. ans = 0;
  43. memset(vis, 0, sizeof(vis));
  44. scanf("%d", &n);
  45. for(int i = 1; i <= n; ++i) {
  46. scanf("%d", &node[i].day);
  47. }
  48. for(int i = 1; i <= n; ++i) {
  49. scanf("%d", &node[i].score);
  50. }
  51. sort(node + 1, node + n + 1);
  52. for(int i = 1; i <= n; ++i) {
  53. int d = node[i].day;
  54. while(d > 0 && vis[d]) {
  55. --d;
  56. }
  57. if(d == 0) {
  58. ans += node[i].score;
  59. } else {
  60. vis[d] = true;
  61. }
  62. }
  63. printf("%d\n", ans);
  64. }
  65. return 0;
  66. }

B. Moving Tables

题意

在以如下方式标记的房间号中,要将桌子在任意两个房间之间移动
rVWl8K.gif
在从第 个房间移动到第 个房间的过程中,这个房间前面的走廊将会被占用,一个房间前的走廊只能放下一张桌子,每张桌子需要挪动 分钟,且桌子可以同时移动(在保证移动不出现冲突的情况下)。

数据范围

题解

这题按照房间的排列方式,可以将第 个房间对应到走廊的第 个位置,要保证走廊不会同时被两张桌子占用的情况下,移动时间最少,也就是求所有桌子占用重叠最多的位置。这样桌子的移动问题,就变成了求解桌子移动占用重叠最大的问题了,也就转化为了线段覆盖问题。
线段覆盖问题有许多变体与应用,这是其中一种:求给定的所有线段覆盖区间中,覆盖最多的次数,一般解法是先离散化每条线段的左右端点,然后在每一条线段的左端点标记一个 ,在每条线段的右端点往右一位标记,然后从头到尾加一遍,求加的的过程中取得的最大值,就是最大重叠数。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  19. #define LL long long
  20. const int maxn = 300;
  21. int T, n, ans, l, r;
  22. int num[maxn];
  23. int main() {
  24. #ifdef LOCAL
  25. freopen("test.txt", "r", stdin);
  26. // freopen("out.txt", "w", stdout);
  27. #endif // LOCAL
  28. ios::sync_with_stdio(false);
  29. scanf("%d", &T);
  30. while(T--) {
  31. ans = 0;
  32. memset(num, 0, sizeof(num));
  33. scanf("%d", &n);
  34. for(int i = 0; i < n; ++i) {
  35. scanf("%d%d", &l, &r);
  36. if(l > r) {
  37. swap(l, r);
  38. }
  39. l = (l + 1) / 2;
  40. r = (r + 1) / 2;
  41. ++num[l];
  42. --num[r + 1];
  43. }
  44. int tmp = 0;
  45. for(int i = 1; i < maxn; ++i) {
  46. tmp += num[i];
  47. ans = max(tmp, ans);
  48. }
  49. printf("%d\n", ans * 10);
  50. }
  51. return 0;
  52. }

C. Wooden Sticks

题意

一台机器要加工 根木棍,第 根木棍有一个长度 与重量 ,对于每根木棍的准备时间计算如下:

  1. 对于加工的第一根木棍,准备时间为
  2. 如果已经加工过一根长为 ,重为 的木棍,接下来加工的长为 重为 的木棍的准备时间为

问最少的准备时间。

数据范围

题解

先将木棍按照从小到大排序(无论以谁为关键字),然后将没有加工过的,长和重都大于当前木棍长、重的木棍进行加工,更新当前的长和重,最后输出重新加工的次数,已经加工过的木棍用 数组来标记。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  19. #define LL long long
  20. const int maxn = 5000 + 100;
  21. struct Node {
  22. int l, w;
  23. };
  24. bool operator<(const Node &a, const Node &b) {
  25. if(a.l == b.l) {
  26. return a.w < b.w;
  27. }
  28. return a.l < b.l;
  29. }
  30. int T, n, ans;
  31. Node node[maxn];
  32. bool vis[maxn];
  33. int pull(int Index) {
  34. int ret = 0;
  35. int l = node[Index].l;
  36. int w = node[Index].w;
  37. for(int i = Index; i < n; ++i) {
  38. if(!vis[i] && node[i].l >= l && node[i].w >= w) {
  39. vis[i] = true;
  40. l = node[i].l;
  41. w = node[i].w;
  42. ++ret;
  43. }
  44. }
  45. return ret;
  46. }
  47. int main() {
  48. #ifdef LOCAL
  49. freopen("test.txt", "r", stdin);
  50. // freopen("out.txt", "w", stdout);
  51. #endif // LOCAL
  52. ios::sync_with_stdio(false);
  53. scanf("%d", &T);
  54. while(T--) {
  55. ans = 0;
  56. memset(vis, 0, sizeof(vis));
  57. scanf("%d", &n);
  58. for(int i = 0; i < n; ++i) {
  59. scanf("%d%d", &node[i].l, &node[i].w);
  60. }
  61. sort(node, node + n);
  62. int cnt = n;
  63. while(cnt != 0) {
  64. for(int i = 0; i < n; ++i) {
  65. if(!vis[i]) {
  66. ++ans;
  67. cnt -= pull(i);
  68. break;
  69. }
  70. }
  71. }
  72. printf("%d\n", ans);
  73. }
  74. return 0;
  75. }

2 月 6 日 贪心练习题解

A. A Magic Lamp

题意

从一个无前导零的 位整数中删除 位数字,使得最后得到的数字最小,若最后的数字存在前导零,则输出忽略这些前导零。

数据范围

题解

只按照数位从大到小删除显然是不对的,例如对于数字 只删除一位数,删除 得到的值为 ,删除 得到的值为 ,这种方法就行不通。从这个例子可以看出,应该从高位往底位删除每一个 的数字,删除 次就可以得到最后的答案,注意如果 的所有数位是非递减的,则要删掉最后一个数字,如果数位为 ,则不应该被删除。
这里的删除可以用 中的链表模拟,或者用 数组来标记是否被删除。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  19. #define LL long long
  20. const int maxn = 1000 + 100;
  21. int m;
  22. char str[maxn];
  23. bool flag[maxn];
  24. int Find() {
  25. for(int i = 0; str[i]; ++i) {
  26. if(str[i] != '0' && !flag[i]) {
  27. for(int j = i + 1; str[j - 1]; ++j) {
  28. if(!flag[j]) {
  29. if(str[i] > str[j]) {
  30. return i;
  31. }
  32. break;
  33. }
  34. }
  35. }
  36. }
  37. return 0;
  38. }
  39. int main() {
  40. #ifdef LOCAL
  41. freopen("test.txt", "r", stdin);
  42. // freopen("out.txt", "w", stdout);
  43. #endif // LOCAL
  44. ios::sync_with_stdio(false);
  45. while(scanf("%s%d", str, &m) != EOF) {
  46. memset(flag, 0, sizeof(flag));
  47. for(int i = 0; i < m; ++i) {
  48. int Index = Find();
  49. flag[Index] = true;
  50. }
  51. int head = -1;
  52. for(int i = 0; str[i]; ++i) {
  53. if(str[i] != '0' && !flag[i]) {
  54. head = i;
  55. break;
  56. }
  57. }
  58. if(head == -1) {
  59. printf("0\n");
  60. } else {
  61. for(int i = head; str[i]; ++i) {
  62. if(!flag[i]) {
  63. printf("%c", str[i]);
  64. }
  65. }
  66. printf("\n");
  67. }
  68. }
  69. return 0;
  70. }

B. Alice and Bob

题意

各有 张卡片, 想要让自己有最多的卡片能够覆盖 的卡片,一张卡片能够覆盖另一张卡片的条件是这张卡片的长 和宽 都不小于另一张卡片的长 和宽 ,且长宽不能交换。总共有 组数据。

数据范围

题解

这个问题的一般解法就是将两个数组从大到小(任选一个作为关键字)排序,对于每个 ,先将所有满足 对应的 值放入 中计数,然后从 中找到大于等于 的最小的数字,删掉这个数字,求能够删掉的最多的数字个数。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  19. #define LL long long
  20. const int maxn = 100000 + 100;
  21. struct Node {
  22. int x, y;
  23. };
  24. bool operator<(const Node &a, const Node &b) {
  25. if(a.x == b.x) {
  26. return a.y > b.y;
  27. }
  28. return a.x > b.x;
  29. }
  30. int T, n, ans;
  31. Node node[maxn], mode[maxn];
  32. map<int, int> mp;
  33. map<int, int>::iterator it;
  34. int main() {
  35. #ifdef LOCAL
  36. freopen("test.txt", "r", stdin);
  37. // freopen("out.txt", "w", stdout);
  38. #endif // LOCAL
  39. ios::sync_with_stdio(false);
  40. scanf("%d", &T);
  41. while(T--) {
  42. scanf("%d", &n);
  43. ans = 0;
  44. mp.clear();
  45. for(int i = 0; i < n; ++i) {
  46. scanf("%d%d", &node[i].x, &node[i].y);
  47. }
  48. for(int i = 0; i < n; ++i) {
  49. scanf("%d%d", &mode[i].x, &mode[i].y);
  50. }
  51. sort(node, node + n);
  52. sort(mode, mode + n);
  53. int Index = 0;
  54. for(int i = 0; i < n; ++i) {
  55. while(Index < n && node[Index].x >= mode[i].x) {
  56. ++mp[node[Index].y];
  57. ++Index;
  58. }
  59. it = mp.lower_bound(mode[i].y);
  60. if(it != mp.end()) {
  61. --it->second;
  62. if(it->second == 0) {
  63. mp.erase(it);
  64. }
  65. ++ans;
  66. }
  67. }
  68. printf("%d\n", ans);
  69. }
  70. return 0;
  71. }

C. Task

题意

与上一题相同,只是在“覆盖卡片数量最多”的条件上加上一条:每完成一个产品,可以获得 ,如果有多解,则输出能够获得的最多的价值。

数据范围

题解

基本思路与上题一样,只是对于附加条件,由于 ,所以无论 如何增加,都不如一个 的增量,因此想要价格最高,则必须将 作为主关键字, 作为第二关键字进行排序。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  19. #define LL long long
  20. const int maxn = 100000 + 100;
  21. struct Node {
  22. int x, y;
  23. };
  24. bool operator<(const Node &a, const Node &b) {
  25. if(a.x == b.x) {
  26. return a.y > b.y;
  27. }
  28. return a.x > b.x;
  29. }
  30. int n, m, ans;
  31. LL price;
  32. Node node[maxn], mode[maxn];
  33. map<int, int> mp;
  34. map<int, int>::iterator it;
  35. int main() {
  36. #ifdef LOCAL
  37. freopen("test.txt", "r", stdin);
  38. // freopen("out.txt", "w", stdout);
  39. #endif // LOCAL
  40. ios::sync_with_stdio(false);
  41. while(scanf("%d%d", &n, &m) != EOF) {
  42. ans = 0;
  43. price = 0;
  44. mp.clear();
  45. for(int i = 0; i < n; ++i) {
  46. scanf("%d%d", &node[i].x, &node[i].y);
  47. }
  48. for(int i = 0; i < m; ++i) {
  49. scanf("%d%d", &mode[i].x, &mode[i].y);
  50. }
  51. sort(node, node + n);
  52. sort(mode, mode + m);
  53. int Index = 0;
  54. for(int i = 0; i < m; ++i) {
  55. while(Index < n && node[Index].x >= mode[i].x) {
  56. ++mp[node[Index].y];
  57. ++Index;
  58. }
  59. it = mp.lower_bound(mode[i].y);
  60. if(it != mp.end()) {
  61. --it->second;
  62. if(it->second == 0) {
  63. mp.erase(it);
  64. }
  65. ++ans;
  66. price += mode[i].x * 500 + mode[i].y * 2;
  67. }
  68. }
  69. printf("%d %lld\n", ans, price);
  70. }
  71. return 0;
  72. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注