知识总结
原理：
每一步都采取局部最优解，取到最终的最优解。
常见时间复杂度
$ O(n)$ 或 $O(nlog (n))$
后者一般带排序。
用法：
-
通过数据规模和题目信息联想贪心算法常见时间复杂度
-
猜测结论
-
验证合理性
- 归纳法
- 反证法（相邻交换法）：如果交换方案中相邻的两个元素/任意的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了。
后悔解法
无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。
（这种算法支持对过往操作的“反悔”，但要求支持的反悔信息和本身贪心的结构是相同的）
考场技巧
1.尝试测试手模样例，并和暴力对拍。
2.多写几个贪心拼凑出最优解。
3.有榜时观察其他人的过题速度，若大家都过不去同一题，先跳过或选择拿暴力等部分分。
随堂练习
T1 小信吃甜筒
题目描述
小信想吃到 $n$ 个巧克力味的甜筒和 $m$ 个草莓味的甜筒，不能多吃。
冰柜里，有 $x$ 个巧克力味甜筒，饱食度分别为 $a_1, a_2,...,a_x$ ，有 $y$ 个草莓甜筒，饱食度分别为 $b_1, b_2,...,b_y$ ，有 $z$ 个原味甜筒，饱食度分别为 $c_1, c_2,...,c_z$ 。小信可以在原味甜筒上加调味料使其变成巧克力味或草莓味。
他想知道在不多吃的情况下能获得的最大饱食值。
思路解析
由于不能多吃，所以我们可以先把原味甜筒加入，然后再取吃巧克力味甜筒和草莓味甜筒其中分别较大的。
然后直接排序选入后的数列，选取 $n+m$ 个最大的数，即可得到最大饱食值。
代码实现
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n, m, l, x, y, z, a[N], b[N], c[N], v[N], flag, ans, ans1;
bool cmp1(int A, int B) {
return A > B;
}
signed main() {
scanf("%lld %lld %lld %lld %lld", &n, &m, &x, &y, &z);
for (int i = 1; i <= x; i++) {
scanf("%lld", &a[i]);
}
for (int i = 1; i <= y; i++) {
scanf("%lld", &b[i]);
}
for (int i = 1; i <= z; i++) {
scanf("%lld", &c[i]);
v[i] = c[i];
}
sort(a + 1, a + 1 + x, cmp1);
sort(b + 1, b + 1 + y, cmp1);
for (int i = 1; i <= n; i++) {
v[i + z] = a[i];
}
for (int i = 1; i <= m; i++) {
v[i + z + n] = b[i];
}
sort(v + 1, v + 1 + n + m + z, cmp1);
for (int i = 1; i <= n + m; i++) {
ans += v[i];
}
printf("%lld", ans);
return 0;
}
T2 替换字母 2
双倍经验: https://www.luogu.com.cn/problem/P2882
题目描述
有长度为 $n$ 的字符串，仅包含小写字母。小信想把字符串变成只包含一种字母。他每次可以选择一种字符 $c$ ，然后把长度最多为 $m$ 的子串中的字符都替换成 $c$ 。
问小信最少需要多少次操作，才能把字符串变成只包含一种字母？
思路解析
我们可以枚举所有可能的字符 $c$ ，然后计算替换操作次数。
对于每个字符 $c$ ，如果当前符合则跳过，否则替换长度为 $m$ 的子串中的字符。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m, ans = inf, cnt;
string a;
int found(char x) {
cnt = 0;
for (int i = 0; i < n;) {
if (a[i] == x) {
i++;
} else {
cnt++;
i += m;
}
}
return cnt;
}
int main() {
cin >> n >> m >> a;
for (char i = 'a'; i <= 'z'; i++) {
ans = min(ans, found(i));
}
printf("%d\n", ans);
return 0;
}
T3 异或与乘积
题目描述
有 $n$ 个数你可以将两个数字异或，最终将所有数字相乘，问总乘积最大是多少
由于答案可能很大，输出对 $1 000 000 007$ 取模后的结果。
思路解析
- 分离出 1 的位置：首先，我们可以找出所有数中为 1 的位，并将这些数分离出来。这些数在异或运算中起到关键作用。
- 处理偶数的情况：偶数 $\oplus$ $1$ = 偶数 $+$ $1$,奇数 $\oplus$ $1$ $=$ 奇数 $-$ $1$因此利用和一定，差小积大：在分组时，我们希望两组的异或结果尽可能接近，这样它们的差值就会小，根据乘法的性质，差值小的两个数相乘会得到更大的乘积。
- 计算乘积：计算组中所有数的乘积。
- 最终乘积：将两组的乘积相乘，并取模 $1000000007$ 。
代码实现
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n, cnt1, a[N], ans = 1, mod = 1e9 + 7;
signed main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
if (a[i] == 1) {
cnt1++;
}
}
for (int i = 1; i <= n; i++) {
if (!cnt1) {
break;
}
if (!(a[i] & 1)) {
cnt1--;
a[i]++;
}
}
for (int i = 1; i <= n; i++) {
ans = (ans % mod * a[i] % mod) % mod;
}
printf("%lld\n", ans);
return 0;
}
T4 国王游戏
题目描述
恰逢 H 国国庆，国王邀请 $n$ 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 $n$ 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
思路解析
本题数据范围较大，因此我们需要使用高精度算法来解决。
对于每一个大臣，他的贡献值就是前面所有大臣的左手的贡献值除以他的右手的贡献值。
如果我们用反证法来验证合理性，那么我们可以找到如果任意交换两个大臣都会使答案更劣，那么我们就证明了答案是最优的。
那么对于每两个大臣，如果将这两个单独处理，则前面大臣的贡献值设为 $x$
则如果将大臣 A 放在大臣 B 前面的贡献值就是 $x·a.l·b.l/b.r$
则如果将大臣 B 放在大臣 A 前面的贡献值就是 $x·b.l·a.l/a.r$
比较这两个贡献值，我们可以得到一个不等式：
若将大臣 A 放在大臣 B 前面贡献值更优，则有 $a.l/b.r<b.l/a.r$ ，化简为 $a.l·a.r<b.l·b.r$
代码实现
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4 + 10;
struct node {
int l, r;
} q[N];
int n, x, y, cina, cinb;
vector<int> a, b;
bool cmp(node A, node B) {
return A.l * A.r < B.l * B.r;
}
namespace High {
void gjc(int x) {
vector<int> te;
int temp = 0;
for (int i = 0; i < a.size(); i++) {
temp += (a[i] * x);
te.push_back(temp % 10);
temp /= 10;
}
while (temp > 0) {
te.push_back(temp % 10);
temp /= 10;
}
a = te;
}
void gjch(int x) {
vector<int> te;
int r = 0;
for (int i = a.size() - 1; i >= 0; i--) {
r = r * 10 + a[i];
te.push_back(r / x);
r %= x;
}
reverse(te.begin(), te.end());
while (!te.empty() && te.back() == 0) {
te.pop_back();
}
if (te.size() > b.size())
b = te;
if (!te.empty() && te.size() == b.size()) {
for (int i = te.size() - 1; i >= 0; i--) {
if (te[i] > b[i]) {
b = te;
break;
} else if (te[i] == b[i])
continue;
else if (te[i] < b[i])
break;
}
}
}
} // namespace High
using namespace High;
signed main() {
scanf("%lld", &n);
scanf("%lld %lld", &x, &y);
for (int i = 1; i <= n; i++) {
scanf("%lld %lld", &cina, &cinb);
q[i].l = cina;
q[i].r = cinb;
}
sort(q + 1, q + 1 + n, cmp);
while (x) {
a.push_back(x % 10);
x /= 10;
}
for (int i = 1; i <= n; i++) {
gjch(q[i].r);
gjc(q[i].l);
}
if (!b.empty()) {
for (int i = b.size() - 1; i >= 0; i--) {
printf("%lld", b[i]);
}
} else {
printf("0");
}
return 0;
}
课后作业
待更
//TODO