算法竞赛进阶指南 基本算法 0x07 贪心

0、AcWing 110. 防晒

题意 ：

• 有 C 头奶牛进行日光浴，第 i 头奶牛需要 minSPF[i] 到 maxSPF[i] 单位强度之间的阳光。
• 每头奶牛在日光浴前必须涂防晒霜，防晒霜有 L 种，涂上第 i 种之后，身体接收到的阳光强度就会稳定为 SPF[i]，第 i 种防晒霜有 cover[i] 瓶。
• 求最多可以满足多少头奶牛进行日光浴。
• 1≤C,L≤2500
• 1≤minSPF≤maxSPF≤1000
• 1≤SPF≤1000

思路 ：

• 按照minSPF递减的顺序把奶牛排序，依次考虑每头奶牛
• 对于每头奶牛，扫描一遍所有的防晒霜，在这头奶牛能用的防晒霜里找SPF值最大的防晒霜
• 我们考虑这一步策略的作用范围扩展到后续其他奶牛之后产生的影响。每瓶防晒霜是否可用，会被minSPF和maxSPF两个条件限制。因为奶牛已被按照minSPF递减排序，所以每一个不低于当前奶牛minSPF值的防晒霜，都不会低于后面其他奶牛的minSPF。也就是说，对于当前奶牛可用的任意两瓶防晒霜x与y，如果SPF[x]
• 另外，每头奶牛对答案的贡献至多是1，即使让当前这头奶牛放弃阳光浴，留下防晒霜给后面的某一头奶牛使用，对答案的贡献也不会变的更大。综上所述，尽量满足当前的奶牛，并选择SPF值尽量大的防晒霜是一个正确的贪心策略
• 关于防晒霜容器的选择，我们需要一个可以二分找到大于某个数值的数值为first的元素，还需要动态地将second为0的元素从容器中删除，因此，我们使用map
• auto spf = spfs.upper_bound(cows[i].second);这句话是在spfs中查找大于cows[i].second的最小元素，设置哨兵是为了让这条语句不返回空。

#include 
#include 
#include 
#define endl '\n'
#define _(a) cout << #a << ": " << (a) << "    "
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2500 + 10;

int c, l;
PII cows[N];
map<int, int> ma;

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> c >> l;
    for (int i = 0; i < c; ++ i) cin >> cows[i].first >> cows[i].second;
    sort(cows, cows + c);
    for (int i = 0; i < l; ++ i) {
        int spf, cnt;
        cin >> spf >> cnt;
        ma[spf] += cnt;
    }
    ma[0] = ma[1001] = c;	// 就算值换成负数也可以ac
    int cnt = 0;
    for (int i = c - 1; i >= 0; -- i) {
        auto pos = ma.upper_bound(cows[i].second);
        -- pos;
        if (pos->first >= cows[i].first && pos->first <= cows[i].second) {
            cnt ++ ;
            if ( -- pos->second == 0) {
                ma.erase(pos);
            }
        }
    }
    cout << cnt;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

1、AcWing 111. 畜栏预定

题意 ：

• 有 N 头牛在畜栏中吃草。
• 每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。
• 给定 N 头牛和每头牛开始吃草的时间 A 以及结束吃草的时间 B，每头牛在 [A,B] 这一时间段内都会一直吃草。
• 当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。
• 求需要的最小畜栏数目和每头牛对应的畜栏方案。

思路 ：

• 按照开始吃草的时间把牛排序
• 维护一个数组S，记录当前每个畜栏安排进去的最后一头牛，最初没有畜栏
• 依次对于每头牛，扫描数组S，找到任意一个畜栏，满足当前的牛开始吃草的时间不早于畜栏中最后一头牛结束吃草的时间，如果这样的畜栏不存在，则为其新建一个畜栏
• 这个贪心算法的复杂度为$O(N^2)$。我们可以用一个小根堆维护每个畜栏最后一头牛结束吃草的时间，尝试把当前的牛安排在堆顶的畜栏中，时间复杂度可以降低到$O(NlogN)$
• 最终，堆的大小就是我们需要的最少畜栏的数量；小根堆中存放的是PII（最后一头牛走的时间、堆的编号）；牛的数组中的是PII-int（开始吃草时间、结束吃草时间、编号）；因此，每头牛对应的畜栏方案就是开一个id数组记录牛编号对应的堆编号

#include 
#include 
#include 
#define endl '\n'
#define _(a) cout << #a << ": " << (a) << "    "
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 5e4 + 10;

int n;
pair<PII, int> cows[N];
priority_queue<PII, vector<PII>, greater<PII>> heap;
int id[N];

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        cin >> cows[i].first.first >> cows[i].first.second;
        cows[i].second = i;
    }
    sort(cows + 1, cows + 1 + n);
    for (int i = 1; i <= n; ++ i) {
        if (heap.empty() || heap.top().first >= cows[i].first.first) {
            PII stall = {cows[i].first.second, heap.size() + 1};
            id[cows[i].second] = heap.size() + 1;
            heap.push(stall);
        } else {
            PII stall = heap.top(); heap.pop();
            id[cows[i].second] = stall.second;
            stall.first = cows[i].first.second;
            heap.push(stall);
        }
    }
    cout << heap.size() << endl;
    for (int i = 1; i <= n; ++ i) cout << id[i] << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

2、AcWing 112. 雷达设备

题意 ：

• 雷达装置均位于海岸线上，且雷达的监测范围为 d，当小岛与某雷达的距离不超过 d 时，该小岛可以被雷达覆盖。
• 现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。

思路 ：

• 按照右端点从小到大排序，注意不是按左端点，因为如果按左端点从小到大，有可能下一段被当前这一段包含在内，那这样的话取右端点就错了；而如果按照右端点从小到大，下一段肯定比当前这段的右端点更右边，不会出问题

#include 
#include 
#include 
using namespace std;
typedef pair<double, double> pdd;
const int N = 1e3 + 10;
const double eps = 1e-6;

pdd seg[N];

bool cmp(pdd u, pdd v) {
    if (u.second != v.second) return u.second < v.second;
    return u.first < v.first;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    double last = -1e20;
    int n, d, cnt = 0;
    cin >> n >> d;
    for (int i = 0; i < n; ++ i) {
        int x, y;
        cin >> x >> y;
        if (y > d) {
            cout << -1;
            return 0;
        }
        double len = sqrt(d * d - y * y);
        seg[i] = {x - len, x + len};
    }
    sort(seg, seg + n, cmp);
    for (int i = 0; i < n; ++ i) {
        if (seg[i].first > last + eps) {
            cnt ++ ;
            last = seg[i].second;
        }
    }
    cout << cnt;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

3、AcWing 114. 国王游戏（高精度乘除比大小）

题意 ：

• 首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。
• 然后，让这 n 位大臣排成一排，国王站在队伍的最前面。
• 排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
• 国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。
• 注意，国王的位置始终在队伍的最前面。

思路 ：

• 分别写出第i个人在第i+1个人前一个他们两个分别的结果res1和res2
• 以及第i个人在第i+1个人后一个他们两个分别的结果res3和res4
• 为了max(res1, res2) <= max(res3, res4)，得出结论 a[i] * b[i] <= a[i + 1] * b[i + 1]
• 假设a全部为9999，$10000^{1000}$显然longlong也放不下，因此需要高精度

#include 
#include 
#include 
using namespace std;
typedef pair<int, int> pii;
const int N = 1e3 + 10;

int n;
pii p[N];

bool cmp(pii a, pii b) {
    return a.first * a.second < b.first * b.second;
}
vector<int> mul(vector<int> &a, int b) {
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); ++ i) {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (t) {
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}
vector<int> div(vector<int> &a, int b) {
    vector<int> c;
    int t = 0;
    bool is_first = true;
    for (int i = a.size() - 1; i >= 0; -- i) {
        t = t * 10 + a[i];
        int x = t / b;
        if (x || !is_first) {
            is_first = false;
            c.push_back(x);
            t %= b;
        }
    }
    reverse(c.begin(), c.end());
    return c;
}
vector<int> chkmx(vector<int> &a, vector<int> &b) {
    if (a.size() > b.size()) return a;
    if (a.size() < b.size()) return b;
    if (vector<int>(a.rbegin(), a.rend()) > vector<int>(b.rbegin(), b.rend())) return a;
    return b;
}

int main() {
    cin >> n;
    for (int i = 0; i <= n; ++ i) {
        cin >> p[i].first >> p[i].second;
    }
    sort(p + 1, p + n + 1, cmp);
    
    vector<int> product;
    product.push_back(1);
    vector<int> mx;
    mx.push_back(0);
    
    for (int i = 0; i <= n; ++ i) {
        if (i) {
            vector<int> tmp = div(product, p[i].second);
            mx = chkmx(mx, tmp);
        }
        product = mul(product, p[i].first);
    }
    for (int i = mx.size() - 1; i >= 0; -- i)
        cout << mx[i];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

4、AcWing 115. 给树染色

题意 ：

• 现在要把这棵树的节点全部染色
• 根节点 R 可以随时被染色；对于其他节点，在被染色之前它的父亲节点必须已经染上了色
• 每次染色的代价为 T×A[i]，其中 T 代表当前是第几次染色。
• 求把这棵树染色的最小总代价。

思路 ：

• 假设权值最大的点为b，如果b的父节点a被染色了，应立即给b染色，即，我们找到了在染色顺序上相邻的两点
• 考虑这对点和其他点的关系，比如点c，那么：
• 1、染色顺序a、b、c，代价为a+2b+3c
• 2、染色顺序c、a、b，代价为c+2a+3c
• 那么，a+2b+3c-(c+2a+3c)=2c-(a+b)，因此，当且仅当$c<\frac{a+b}{2}$时，我们应该先染a和b，再染c
• 因此，将a和b当作一个点，权值为平均值
• 进一步推广，如果有两组分别在染色时相邻的一段的点，可以将这两组分别看成两个点，其权值为组内所有点权值的平均值
• 因此，最终做法为，每次找出当前权值最大的非根节点，其染色顺序紧随其父节点之后，因此，将该点合并到父节点，并更新父节点的权值，直到所有点都被合并到根节点上
• 如果按照上述方案，最终分值不易被计算，因此，在点合并时，我们实时更新当前的权值和：
• 最初所有点各自为一组，权值和$S={\sum }_{i=1}^n{a}_i\ast 1$
• 接下来每次会把两组的点合并，将其中一组点接到另一组点的后面，比如两组点分别是$x_i$和$y_i$，我们将y_i接到x_i之后，则y_i中每个点所乘的系数均会增加一个相同的偏移量，且这个偏移量就是x_i中点的个数，假设为k，那么合并之后，总的权值直接加上$k\ast \sum y_i$即可

代码实现：

• 我们将每一个节点看成一个结构体，结构体内包含这个点的父节点、所处的组的点的个数、所处的组的权值之和、所处的组的平均权值
• 一共需要合并n-1次，每次找到当前所在组的权值最大的非根节点的这个组的组内父节点后，找到这个点的父节点，答案加上这个点所在的组的权值乘其父节点所在组的点的个数
• 然后使这个点的父节点身份失效（avg=-1），并将所有以这个点为父节点的点的父节点更改为父节点的父节点，最后更新这个父节点所在组的点的数量，这个组的平均权值

#include 
using namespace std;
const int N = 1e3 + 10;

struct Node {
    int v, s, p;
    double avg;
}nodes[N];

int n, root;

int find() {
    double mx = 0;
    int p;
    for (int i = 1; i <= n; ++ i) {
        if (i != root && nodes[i].avg > mx) {
            mx = nodes[i].avg;
            p = i;
        }
    }
    return p;
}

int main() {
    cin >> n >> root;
    int ans = 0;
    for (int i = 1; i <= n; ++ i) {
        cin >> nodes[i].v;
        nodes[i].avg = nodes[i].v;
        nodes[i].s = 1;
        ans += nodes[i].v;
    }
    for (int i = 0; i < n - 1; ++ i) {
        int a, b;
        cin >> a >> b;
        nodes[b].p = a;
    }
    for (int i = 0; i < n - 1; ++ i) {
        int p = find();
        int father = nodes[p].p;
        ans += nodes[father].s * nodes[p].v;
        nodes[p].avg = -1;
        for (int j = 1; j <= n; ++ j) {
            if (nodes[j].p == p) {
                nodes[j].p = father;
            }
        }
        nodes[father].v += nodes[p].v;
        nodes[father].s += nodes[p].s;
        nodes[father].avg = nodes[father].v * 1.0 / nodes[father].s;
    }
    cout << ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54