贪心

🔗 引用站外地址，请注意甄别
第二课：贪心
517coding

A：最小字典序

🔗 引用站外地址，请注意甄别
最小字典序
517coding

思路

贪心的去选取

例如样例 ACDBCB

开头和结尾相比，A 小，B 大，选择 A，此时 $t$ 为 A

字符串变成 CDBCB，B 小，C大，选 B，此时 $t$ 为 AB

看似只要开头和结尾不同就只要选择小的哪个就 OK 了，但是如果开头和结尾相同呢？

此时字符串为 CDBC，选择左边的 C 还是右边的 C 就值得思考了。

如果选择左边，接下来 $t$ 最终会变成 ABCCBD ，显然不是最优的，那么就应该先选择右边的 C，最终得到的才是正确的答案

正解

如果开头和结尾不同，那么就取较小的字符

当一个字符串的开头和结尾相同时，就要两边同时往里面看，一直看到两边不同为止。

假设向里面看到的两个不同的位置的字符从左到右分别是 $A$ 和 $B$ ，那么如果 $A$ 小于 $B$，就先取左边的开头，如果 $B$ 小于 $A$ ，那么就取右边的结尾

这样做的复杂度为 $O(n^2)$，而 $n$ 最大只有 $2000$，完全可以接受

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
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    string s;
    cin >> s;
    string t = "";
    int l = 0, r = n - 1;
    while(l <= r) {//两个变量维护开头和结尾
        //如果开头和结尾不同，就取较小的一个
        if (s[l] < s[r]) t += s[l], l++;
        else if (s[r] < s[l]) t += s[r], r--;
        else {
            //两个变量同时往里面缩
            int idx1 = l, idx2 = r;
            while(idx1 <= idx2 && s[idx1] == s[idx2]) idx1++, idx2--;
            if (s[idx1] < s[idx2]) t += s[l], l++;
            else t += s[r], r--;
        }
    }
    //别忘了每80个字符换行一次
    int len = t.size();
    for (int i = 0; i < len; i++) {
        cout << t[i];
        if ((i + 1) % 80 == 0) printf("\n");
    }
    return 0;
}

B：雷达

🔗 引用站外地址，请注意甄别
雷达
517coding

直接按 $x$ 排序

直觉告诉我们，可以按照点的 $x$ 排序，这样的话这个雷达不仅可以把这个点覆盖，还有更多的机会取覆盖更右边的点

但是会有一个问题

假设有连个点，分别为 $C_1,C_2$，能够覆盖他们的雷达的最远位置分别是 $A_1,A_2$ ，它们格子距离雷达的长度分别是 $l_1,l_2$

那么如果选择了 $A_1$ ，就会错过 $C_2$ ，原因是因为，$C_2$ 距离 $x$ 轴是包含了高度的，这样计算的话，如果 $l_1$ 就等于 $d$ ，也就是雷达的最大半径，$A_1$ 就无法覆盖。原来的贪心策略出现了问题

正解

可以换一个角度思考这个问题

对于每一个点，设能够覆盖到它的最远的雷达分别为 $B_1,B_2 $

那么这两个点就构成了一个区间

如图，红色的点的位置为 $(x,y)$，设点 $P$ 的左边为 $(x,y)$ ，那么 $B_1,B2$ 的 $y$ 坐标肯定都是 $0$ ，$x$ 坐标分别为 $x-\sqrt{d^2-y^2}$ 和 $x+\sqrt{d^2-y^2}$（关于原理论证，详见下）

也就是说，在 区间$[x-\sqrt{d^2-y^2}，x+\sqrt{d^2-y^2}]$ 内任意选一个雷达，都可以覆盖掉这个点

那么就可以得出这么一个结论，所有的点都可以转化成若干段区间。

原问题就被转换成了一个新的问题，即给你若干个区间，选择最少的点，使得每个区间内都有点

新问题中的“点”其实就是雷达，根据模型转换的思想，就不需要管原问题了

论证

还是上面这个图

设左边黄色的线上的点是 $B_1$ ，右边黄色的线上的点是 $B_2$ ，红色的点为 $P$

我们观察到到三角形 $PB_1B_2$ 中的一条紫色的先把这个三角形分成两半，而且是两个直角三角形

直角三角有一个至关重要的结论——勾股定理，也就是 $a^2+b^2=c^2$

那么，现在我们把这个公式倒过来用

设点 $P$ 的坐标为 $(x,y)$

已知紫色的线于 $x$ 轴垂直，设垂足为 $Q$

已知三角形 $PB_1Q$ 的斜边长度为 $d$ ，高的长度为 $y$ ，在勾股定理中分别代表 $a$ 和 $c$

那么就可以得到 $d^2$ 和 $y^2$ ，即勾股定理中的 $a^2$ 和 $c^2$

那么就已知 $a^2$ 和 $c^2$

$\because a^2+b^2=c^2$

$\therefore b^2=c^2-a^2$

$\therefore b=\sqrt{c^2-a^2}$

数学语言不太标准，勿喷

区间覆盖问题

通过模型转化，得到以下新问题

给你若干个区间，求至少多少个点，可以覆盖所有区间

因为选择右端点可以尽可能多的覆盖区间，所以贪心的策略就是只选右端点

一定存在这样一种答案，所有选择的点都是右端点

按照右端点排序

用变量 $R$ 维护当前选区的右端点

如果下一个区间的左端点小于 $R$ ，那么就不用管这个区间了，这个区间会直接被覆盖

无解的情况

当我们发现输入的点的 $y$ 坐标大于 $d$ 时，就是误解

不推荐在输入时 break ，尤其是多组数据，会出问题

注意：这道题目有负数，但只要特判无解的时候加上 fabs 或者 abs 就行了

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
#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
double x[N], y[N];

int n, r;
//转换后的区间
pair<double, double> a[N];
void init() {
    for(int i = 1;i <= n; i++) {
        double tmp = sqrt(r * r - y[i] * y[i]);
        a[i].first= x[i] - tmp;
        a[i].second = x[i] + tmp;
    }
}

bool cmp(pair<double, double> _x, pair<double, double> _y) {
    return _x.second < _y.second;
}
int main() {
    scanf("%d%d", &n, &r);
    int flag = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%lf%lf", &x[i], &y[i]);
        if (fabs(y[i]) > r) flag = 1;//注意y[i]可能是负数
    }
    //特判无解
    if (flag == 1) {
        printf("-1\n");
        return 0;
    }
    init();
    sort(a + 1, a + n + 1, cmp);//排序，右端点越大越靠前
    double R = a[1].second;
    int ans = 1;
    for(int i = 1;i <= n; i++)
        if(a[i].first > R) R = a[i].second, ans++;
    printf("%d\n", ans);
    return 0;
}

C：机器分配

🔗 引用站外地址，请注意甄别
机器分配
517coding

把机器和任务转化成点

我们可以把机器和任务都转化成平面直角坐标系上的点

一个机器要想完成一个任务，那么代表这个机器的点必须在代表任务的点的上方或右方或右上方

从分数入手

题目中说完成一个任务的分数为 $500x+2y$

显然，$x$ 增加 $1$ ，分数就会增加 $500$ ，$y$ 增加 $1$ ，分数就会增加 $2$ ，而 $y$ 最大只有 $100$

这样就可以得出一个结论：优先去做 $x$ 较大的任务

但是题目的第一需求时完成任务的数量较多，第二需求是分数较多

优先完成 $x$ 较大的任务会不会导致完成的任务的数量变少呢？

肯定是会影响答案的

那么在任务选择机器的时候，就应该选择最合适的机器，性价比最高的机器

就是说只要这个机器能完成当前的任务就先顶了，没必要让机器大出任务很多

正解

把机器和任务分别都按照 $x$ 从大到小排序

在任务数组里面设置一个 $i$ 指针，在机器数组里面设置一个 $j$ 指针，因为数组已经按照 $x$ 排序，所以可以让 $j$ 不断滑动，滑动到刚好 $j$ 位置的 $x$ 大于等于当前任务的 $x$ 并且 $j$ 位置的 $x$ 小于当前任务的 $x$

得到这样的一个 $j$ 后，只需要在 [$1,j$] 区间中找一个最合适的机器即可（假设下标从 $1$ 开始）

此时，机器的 $x$ 已经没有用了，因为我已经知道 [$1,j$] 区间中所有的机器的 $x$ 都大于当前的任务的 $x$ ，所有不用再考虑 $x$ 了。为了性价比最高，应当选择 [$1,j$] 区间中 $y$ 最小的机器，并且这个机器的 $y$ 大于任务的 $y$

注意开 long long

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
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int cnt[110];
struct node {
    int x, y;
    //重载小于号运算符
    bool operator < (const node &cmp) const {
        if (x != cmp.x) return x > cmp.x;
        return y > cmp.y;
    }
} a[N], b[N];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].x, &a[i].y);
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &b[i].x, &b[i].y);
    }
    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);
    //注意开long long
    long long ans1 = 0, ans2 = 0;
    for (int i = 1, j = 1; i <= m; i++) {
        while(j <= n && a[j].x >= b[i].x) {
            cnt[a[j].y]++;//桶
            j++;
        }
        //利用桶排序的效率更高
        for (int k = b[i].y; k <= 100; k++) {
            if (cnt[k]) {
                ans1++;
                ans2 += 500LL * b[i].x + 2LL * b[i].y;
                cnt[k]--;
                break;
            }
        }
    }
    printf("%lld %lld\n", ans1, ans2);
    return 0;
}