贪心
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
贪心
先上题理解一下贪心咋用的：
题目大意：你有\(n\)种牌，第i种牌的数目为\(c_{i}\)。另外有一种特殊的牌：joker，它的数目是\(m\)。你可以用每种牌各一张来组成一套牌，也可以用一张 joker 和除了某一种牌以外的其他牌各一张组成1套牌。比如，当 \(n=3\) 时，一共有4种合法的套牌：{1,2,3}，{J,2,3}，{1,J,3}，{1,2,J}。给出 \(n\),\(m\)和\(c_{i}\)，你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里（可以有牌不使用）。
显然二分+贪心；
每次二分一个套牌数目，设它为\(std\)。贪心的使用 joker。对于每种牌，如果它的数目\(c_{i}\)大于等于\(std\)，那么不用管它，这种牌的数目是足够的。如果小于\(std\)，那我们就要使用 joker 了（能放则放，贪心思想）。
我们用一个\(tmp\)容器记录一下joker使用的次数，然后考虑\(tmp\)等于多少时，这个\(std\)不符合条件，也就是求一下\(tmp\)的限制条件。
\(1.tmp <= m\)；
\(2.tmp<=std\)。
第一个是因为最多只有\(m\)张joker，第二个是因为每套牌中只能出现一张 joker。
那为什么这么贪心的放牌，是正确的呢? 因为我们有一个限制条件\(tmp <= std\)，我们不管 joker 到底出现在哪，只管用了几张，只要这套牌用了 joker ，这套牌别的位置就用给出的牌填上去。那如果别的牌不够呢，填不上去咋办？
假设我们现在紫色的牌只有四张，黑牌代表 joker ，如果要填满就得用两张 joker ，我们发现第三套牌（第三行）出现了两张 joker ，不符合题意了，但是这时候 \(tmp > std\)，我们就可以直接判断不合法了。
#include <iostream>
#include <cstdio>
#include <cctype>
#define mid ((l + r + 1) >> 1)
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 55, inf = 7e8 + 5e7 + 1;
int n, m, l, r, num;
int c[N];
bool judge(int std) {
int tmp = 0, rest = std;
for(int i = 1;i <= n; i++) {
if(c[i] >= std) continue;
tmp += (std - c[i]); rest -= (std - c[i]);
if(tmp > m || rest < 0) return 0;
}
return 1;
}
int main() {
n = read(); m = read();
for(int i = 1;i <= n; i++) c[i] = read(), num += c[i];
l = 1, r = inf;
while(l < r) {
if(judge(mid)) l = mid;
else r = mid - 1;
}
printf("%d", l);
return 0;
}
贪心与排序
有一些题你可以轻易地看出是贪心，但是不知道该怎么贪。因为他会给你一些条件，或者属性，你得确定一个正确的贪心顺序。
看题理解：
题目大意：国王会给每个大臣发金币，每个大臣左右手都有两个数字,国王也有，它影响大臣们得到金币的数量。一个大臣得到金币的数量定义为：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。你要确定大臣的排列顺序，使得获得奖赏最多的大臣，拿到的金币最少。
用\(a_{i}\)，\(b_{i}\)表示第\(i\)个大臣左右手上的数字。考虑怎么排序。
现在有两个大臣\(i\), \(j\)。
情况一：我们先给\(i\)发，再给\(j\)发，那么他们得到的金币最多就是：\(max(\frac{sum}{b_{i}} , \frac{sum * a_{i}}{b_{j}})\)，设为\(max(t1, t2)\)。
情况二：我们先给\(j\)发，再给\(i\)发，那么他们得到的金币最多就是：\(max(\frac{sum}{b_{j}} , \frac{sum * a_{j}}{b_{i}})\)，设为\(max(t3, t4)\)。
显然，$ t2 > t3, t4 > t1 $
所以我们如果要让情况一的答案小于情况二的答案，我们只需让\(t2 > t4\)。
\(\frac{sum * a_{i}}{b_{j}} > \frac{sum * a_{j}}{b_{i}}\)化简可得：\(a_{i} * b_{i} > a_{j} * b_{j}\)。
所以我们按这个排序后，根据规则发金币就好啦。
但是还有一个ex的地方，这题用高精，我吐了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5;
int n, a, b, j;
int na[N], naw[N], old[N], ol[N], ans1[N], ans2[N];
struct poe { int mul, x, y; } e[N];
int cmp(poe a, poe b) {
return a.mul < b.mul;
}
void mul(int x) {
memset(ol, 0, sizeof(ol));
int k = 0;
while(x) {
naw[++k] = x % 10;
x /= 10;
}
ol[0] = old[0] + k;
for(int i = 1;i <= old[0]; i++) {
int x = 0;
for(int j = 1;j <= k; j++) {
ol[i + j - 1] = old[i] * naw[j] + x + ol[i + j - 1];
x = ol[i + j - 1] / 10;
ol[i + j - 1] %= 10;
}
ol[i + k] = x;
}
while(ol[ol[0]] == 0 && ol[0] > 0) {
ol[0]--;
}
old[0] = ol[0];
for(int i = 1;i <= ol[0]; i++) {
old[i] = ol[i];
}
}
void cut(int x) {
memset(ans1, 0, sizeof(ans1));
int q = 0;
for(int i = old[0];i >= 1; i--) {
q *= 10;
q += old[i];
ans1[i] = q / x;
if(ans1[0] == 0 && ans1[i] != 0) {
ans1[0] = i;
}
q %= x;
}
}
int compare() {
if(ans1[0] == ans2[0]) {
for(int i = ans1[0]; i >= 1; i--) {
if(ans1[i] > ans2[i]) return 1;
if(ans1[i] < ans2[i]) return 0;
}
}
if(ans1[0] > ans2[0]) return 1;
if(ans1[0] < ans2[0]) return 0;
}
void copy() {
ans2[0] = ans1[0];
for(int i = 1;i <= ans1[0]; i++) {
ans2[i] = ans1[i];
}
}
int main() {
old[0] = 1; old[1] = 1; ans1[0] = 0;
scanf("%d %d %d", &n, &e[0].x, &e[0].y);
for(int i = 1;i <= n; i++) {
scanf("%d %d", &e[i].x, &e[i].y);
e[i].mul = e[i].x * e[i].y;
}
sort(e + 1, e + n + 1, cmp);
for(int i = 1;i <= n; i++) {
mul(e[i - 1].x);
cut(e[i].y);
if(compare()) {
copy();
}
}
for(int i = ans2[0]; i >= 1; i--) {
cout << ans2[i];
}
return 0;
}
P2878 [USACO07JAN]Protecting the Flowers S
题目大意：有n头奶牛跑到花园里去吃花儿了，它们分别在距离牛圈T分钟处吃花儿，每分钟会吃掉D朵的花儿，现在要将它们给弄回牛圈，但是每次只能弄一头回去，来回用时总共为2*T分钟，在这段时间内，其它的奶牛会继续吃花儿，速度保持不变，当然正在被赶回牛圈的奶牛就不能吃了！现在要搞一个送奶牛的顺序，求奶牛吃掉花儿的最少朵数！
和刚刚那个题的思路一样，现在有两头奶牛\(i\),\(j\)。
情况一：先送奶牛\(i\)，再送奶牛\(j\)，他们这段时间内他们吃掉的花儿朵数：\(2 * T_{i} * D_{j}\)；
情况二：先送奶牛\(j\)，再送奶牛\(i\)，他们这段时间内他们吃掉的花儿朵数：\(2 * T_{j} * D_{i}\)。
我们如果要让情况一的答案小于情况二的答案，就让\(2 *T_{i} * D_{j} < 2 *T_{j}* D_{i}\)，化简可得：\(\frac{T_{i}}{D_{i}} < \frac{T_{j}}{D_{j}}\)。
按这个排序就好了。
#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 1e5 + 5;
int n, sum[N];
long long ans;
struct cow { int t, d; double skr; } a[N];
int cmp(cow x, cow y) { return x.skr < y.skr; }
int main() {
n = read();
for(int i = 1;i <= n; i++) a[i].t = read(), a[i].d = read(), a[i].skr = (double)a[i].t / a[i].d;
std::sort(a + 1, a + n + 1, cmp);
for(int i = 1;i <= n; i++) sum[i] = sum[i - 1] + a[i].d;
long long tim = 0;
for(int i = 1;i <= n; i++) {
tim = 2 * a[i].t;
ans += tim * (sum[n] - sum[i]);
}
printf("%lld", ans);
return 0;
}
数位贪心
题目大意：从小于等于\(m\)的数中选一个数，经过\(n\)次运算（&，|，^）后，使得到的数最小，输出这个得到的数。
一看见这些运算符，感觉要用二进制。
答案的二进制上的某一位只与一开始的数对应的那一位有关，因为这几种运算都不会进位的。我们对开始的数的二进制从高位到低位贪心，如果这一位的二进制数经过\(n\)次运算后不变，0还是0，1还是1，并且这一位选了1后小于等于\(m\)，那这一位就选1；其他情况都选0。
这一位选了1后小于等于\(m\)：这个应该很好理解。
这一位的二进制数经过\(n\)次运算后不变，0还是0，1还是1：如果0经过运算后为1，那这一位不放1更优。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5 + 5;
int n, m, now, ans;
struct oper { int op, t; } a[N];
int calc(int bin, int x) {
for(int i = 1;i <= n; i++) {
int y = (a[i].t >> bin) & 1;
if(a[i].op == 1) x &= y;
if(a[i].op == 2) x |= y;
if(a[i].op == 3) x ^= y;
}
return x;
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 1;i <= n; i++) {
char ch[5]; int x;
cin >> ch; scanf("%d", &x);
if(ch[0] == 'A') a[i].op = 1, a[i].t = x;
if(ch[0] == 'O') a[i].op = 2, a[i].t = x;
if(ch[0] == 'X') a[i].op = 3, a[i].t = x;
}
now = 0, ans = 0;
for(int i = 30; ~i ; i--) {
int res0 = calc(i, 0);
int res1 = calc(i, 1);
if(now + (1 << i) <= m && res0 < res1) { now += 1 << i; ans += res1 << i; }
else { ans += res0 << i; }
}
printf("%d", ans);
return 0;
}
题目大意：给定一个长度为n的序列a[1],a[2],...,a[n]，请将它划分为m段连续的区间，设第i段的费用c[i]为该段内所有数字的异或和，则总费用为c[1] or c[2] or ... or c[m]。请求出总费用的最小值。
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 5e5 + 5;
int n, m;
bool vis[N];
long long x, ans, sum[N];
int main() {
n = read(); m = read();
for(int i = 1;i <= n; i++) x = read(), sum[i] = sum[i - 1] ^ x;
for(int i = 61;i >= 0; i--) {
int tot = 0;
for(int j = 1;j <= n; j++) {
if(!vis[j] && !((sum[j] >> i) & 1)) tot++;
}
if(tot >= m && !((sum[n] >> i) & 1)) {
for(int j = 1;j <= n; j++) if((sum[j] >> i) & 1) vis[j] = 1;
}
else ans |= (1ll << i);
}
printf("%lld", ans);
return 0;
}
贪心和堆
题目大意：有\(n\)堆果子，每次合并两堆，花费的代价是这两堆果子的数量之和，求最小代价。
这道题挺简单的，每次贪心的选出两堆数量最小的果子合并就好了。
加强版优先队列过不了，优先队列是\(O(nlogn)\)的，要手写两个队列，一个存原来的堆数，一个存合并后的堆数，这样做复杂度是\(O(n)\)的。
#include <iostream>
#include <cstdio>
#include <cctype>
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 1e8;
int l, r, ll, rr, n, a[100005];
long long x, y, xx, yy, q[N], w[N];
long long ans;
int main() {
n = read();
for(int i = 1, x;i <= n; i++) x = read(), a[x]++;
l = 1; r = 0; ll = 1; rr = 0;
for(int i = 1;i <= 100000; i++) {
while(a[i] != 0) q[++r] = i, a[i]--;
}
while(l <= r || ll < rr) {
x = y = xx = yy = 1e12;
if(r - l + 1 > 0) x = q[l], y = q[l + 1];
if(rr - ll + 1 > 0) xx = w[ll], yy = w[ll + 1];
if(y == 0) y = 1e12; if(yy == 0) yy = 1e12;
if(y <= xx) {
ans += x + y; w[++rr] = x + y; l += 2;
}
else if(yy <= x) {
ans += xx + yy; w[++rr] = xx + yy; ll += 2;
}
else if(x <= xx && xx < y) {
ans += x + xx; w[++rr] = x + xx; l++; ll++;
}
else if(xx <= x && x < yy) {
ans += x + xx; w[++rr] = x + xx; l++; ll++;
}
}
printf("%lld", ans);
return 0;
}