@Dmaxiya 2020-12-12T07:43:12.000000Z 字数 8104 阅读 1517

贪心练习题解

Hello_World

贪心

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

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

2 月 5 日贪心练习题解

A. Doing Homework again

题意

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

数据范围

$1\leq n\leq1000\\1\leq day_i\leq1000$

题解

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

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
struct Node {
    int day;
    int score;
};
bool operator<(const Node &a, const Node &b) {
    if(a.score == b.score) {
        return a.day > b.day;
    }
    return a.score > b.score;
}
int T, n, ans;
Node node[maxn];
bool vis[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        ans = 0;
        memset(vis, 0, sizeof(vis));
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &node[i].day);
        }
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &node[i].score);
        }
        sort(node + 1, node + n + 1);
        for(int i = 1; i <= n; ++i) {
            int d = node[i].day;
            while(d > 0 && vis[d]) {
                --d;
            }
            if(d == 0) {
                ans += node[i].score;
            } else {
                vis[d] = true;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

B. Moving Tables

题意

在以如下方式标记的房间号中，要将桌子在任意两个房间之间移动

在从第 $i$ 个房间移动到第 $j$ 个房间的过程中，这个房间前面的走廊将会被占用，一个房间前的走廊只能放下一张桌子，每张桌子需要挪动 $10$ 分钟，且桌子可以同时移动（在保证移动不出现冲突的情况下）。

数据范围

$1\leq n\leq200$

题解

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

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 300;
int T, n, ans, l, r;
int num[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        ans = 0;
        memset(num, 0, sizeof(num));
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) {
            scanf("%d%d", &l, &r);
            if(l > r) {
                swap(l, r);
            }
            l = (l + 1) / 2;
            r = (r + 1) / 2;
            ++num[l];
            --num[r + 1];
        }
        int tmp = 0;
        for(int i = 1; i < maxn; ++i) {
            tmp += num[i];
            ans = max(tmp, ans);
        }
        printf("%d\n", ans * 10);
    }
    return 0;
}

C. Wooden Sticks

题意

一台机器要加工 $n$ 根木棍，第 $i$ 根木棍有一个长度 $l_i$ 与重量 $w_i$ ，对于每根木棍的准备时间计算如下：

对于加工的第一根木棍，准备时间为 $1$ ；

如果已经加工过一根长为 $l$ ，重为 $w$ 的木棍，接下来加工的长为 $l'$ 重为 $w'$ 的木棍的准备时间为 $0$ ；

问最少的准备时间。

数据范围

$1\leq n\leq5000\\0\leq l_i,w_i\leq10000$

题解

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

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 5000 + 100;
struct Node {
    int l, w;
};
bool operator<(const Node &a, const Node &b) {
    if(a.l == b.l) {
        return a.w < b.w;
    }
    return a.l < b.l;
}
int T, n, ans;
Node node[maxn];
bool vis[maxn];
int pull(int Index) {
    int ret = 0;
    int l = node[Index].l;
    int w = node[Index].w;
    for(int i = Index; i < n; ++i) {
        if(!vis[i] && node[i].l >= l && node[i].w >= w) {
            vis[i] = true;
            l = node[i].l;
            w = node[i].w;
            ++ret;
        }
    }
    return ret;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        ans = 0;
        memset(vis, 0, sizeof(vis));
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) {
            scanf("%d%d", &node[i].l, &node[i].w);
        }
        sort(node, node + n);
        int cnt = n;
        while(cnt != 0) {
            for(int i = 0; i < n; ++i) {
                if(!vis[i]) {
                    ++ans;
                    cnt -= pull(i);
                    break;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

2 月 6 日贪心练习题解

A. A Magic Lamp

题意

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

数据范围

$1\leq\left|n\right|\leq1000,0\leq m\leq\left|n\right|$

题解

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

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
int m;
char str[maxn];
bool flag[maxn];
int Find() {
    for(int i = 0; str[i]; ++i) {
        if(str[i] != '0' && !flag[i]) {
            for(int j = i + 1; str[j - 1]; ++j) {
                if(!flag[j]) {
                    if(str[i] > str[j]) {
                        return i;
                    }
                    break;
                }
            }
        }
    }
    return 0;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%s%d", str, &m) != EOF) {
        memset(flag, 0, sizeof(flag));
        for(int i = 0; i < m; ++i) {
            int Index = Find();
            flag[Index] = true;
        }
        int head = -1;
        for(int i = 0; str[i]; ++i) {
            if(str[i] != '0' && !flag[i]) {
                head = i;
                break;
            }
        }
        if(head == -1) {
            printf("0\n");
        } else {
            for(int i = head; str[i]; ++i) {
                if(!flag[i]) {
                    printf("%c", str[i]);
                }
            }
            printf("\n");
        }
    }
    return 0;
}

B. Alice and Bob

题意

$Alice$ 和 $Bob$ 各有 $n$ 张卡片， $Alice$ 想要让自己有最多的卡片能够覆盖 $Bob$ 的卡片，一张卡片能够覆盖另一张卡片的条件是这张卡片的长 $x$ 和宽 $y$ 都不小于另一张卡片的长 $x'$ 和宽 $y'$ ，且长宽不能交换。总共有 $T$ 组数据。

数据范围

$T\leq40,N\leq10^5\\h_i,w_i\leq10^9$

题解

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

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
struct Node {
    int x, y;
};
bool operator<(const Node &a, const Node &b) {
    if(a.x == b.x) {
        return a.y > b.y;
    }
    return a.x > b.x;
}
int T, n, ans;
Node node[maxn], mode[maxn];
map<int, int> mp;
map<int, int>::iterator it;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        ans = 0;
        mp.clear();
        for(int i = 0; i < n; ++i) {
            scanf("%d%d", &node[i].x, &node[i].y);
        }
        for(int i = 0; i < n; ++i) {
            scanf("%d%d", &mode[i].x, &mode[i].y);
        }
        sort(node, node + n);
        sort(mode, mode + n);
        int Index = 0;
        for(int i = 0; i < n; ++i) {
            while(Index < n && node[Index].x >= mode[i].x) {
                ++mp[node[Index].y];
                ++Index;
            }
            it = mp.lower_bound(mode[i].y);
            if(it != mp.end()) {
                --it->second;
                if(it->second == 0) {
                    mp.erase(it);
                }
                ++ans;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Task

题意

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

数据范围

$1\leq n,m\leq10^5\\0<x_i<1440,0\leq y_i\leq100$

题解

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

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
struct Node {
    int x, y;
};
bool operator<(const Node &a, const Node &b) {
    if(a.x == b.x) {
        return a.y > b.y;
    }
    return a.x > b.x;
}
int n, m, ans;
LL price;
Node node[maxn], mode[maxn];
map<int, int> mp;
map<int, int>::iterator it;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        ans = 0;
        price = 0;
        mp.clear();
        for(int i = 0; i < n; ++i) {
            scanf("%d%d", &node[i].x, &node[i].y);
        }
        for(int i = 0; i < m; ++i) {
            scanf("%d%d", &mode[i].x, &mode[i].y);
        }
        sort(node, node + n);
        sort(mode, mode + m);
        int Index = 0;
        for(int i = 0; i < m; ++i) {
            while(Index < n && node[Index].x >= mode[i].x) {
                ++mp[node[Index].y];
                ++Index;
            }
            it = mp.lower_bound(mode[i].y);
            if(it != mp.end()) {
                --it->second;
                if(it->second == 0) {
                    mp.erase(it);
                }
                ++ans;
                price += mode[i].x * 500 + mode[i].y * 2;
            }
        }
        printf("%d %lld\n", ans, price);
    }
    return 0;
}

贪心练习题解

贪心

2 月 5 日 贪心练习题解

A. Doing Homework again

题意

数据范围

题解

过题代码

B. Moving Tables

题意

数据范围

题解

过题代码

C. Wooden Sticks

题意

数据范围

题解

过题代码

2 月 6 日 贪心练习题解

A. A Magic Lamp

题意

数据范围

题解

过题代码

B. Alice and Bob

题意

数据范围

题解

过题代码

C. Task

题意

数据范围

题解

过题代码

内容目录

2 月 5 日贪心练习题解

2 月 6 日贪心练习题解