题解 CF321B 【Ciel and Duel】

[题目大意](https://www.luogu.org/problem/CF321B) 这道题目难处理的是我方的牌可以打完，也可以不打完，并且由样例二可以发现并不是出数值相近的牌就能赢，很像是 dp （事实上也是） 那到底如何出牌才能收益最大呢？考虑全两种情况：打完自己的牌、不打完自己的牌。 --- _策略一：打爆对方所有牌_ 那么很明显此时先攻击 DEF 更优。因为我们期望的是打完所有牌，如果自己还有剩余直接构成真伤。 如果先攻击 ATK 很可能出现打不动 DEF 的尴尬局面。所以我们每次找与对方 DEF 最接近的牌打出，然后再找和对方 ATK 最相近的牌打。最后，如果还有剩余直接累加答案就好了。 为什么找和对方 ATK 最接近的牌打呢？貌似拿自己最大的打别人最小的更划算啊 其实，这就是我们的另一种策略了。因为不打完自己的所有牌，那就必须让打出的牌造成的伤害最大嘛 _策略二：中途退出_ 这种策略下我们不打 DEF，因为要把牌都留着打 ATK。而且如果想着造成 ATK 伤害最大下同时试着打完 DEF 再造成真伤，就是策略一策略二两头都没顾着了，很容易被 hack --- 通过简述两种情况下的策略，我们很容易发现它们都能被 hack。 犹豫不定，想打完所有牌可见样例二 每次选最大打最小，容易构造： ``` 3 4 ATK 1 ATK 2 ATK 3 4 3 2 2 ``` 所以，我们要考虑全两种情况，把两种贪心策略中择优啊 当然，dp 和 最小费用最大流都可做，可以参考 CF 的官方题解。 本题还有的坑点是力量值是非负的，初值要设为 `-1` code : ```cpp #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 100003; int n, m; int totAtk, totDef; int xAtk[N]; int yAtk[N], yDef[N]; //totAtk totDef为对方手中ATK与DEF的数目，便于排序 //xAtk[]是我方卡牌数组 //yAtk[] yDef[]是对方卡牌数组 int copy_xAtk[N]; int copy_yAtk[N], copy_yDef[N]; //这里有上述三个数组的备份 //为了防止做完一种策略对后面策略中数组的影响 //rush便是打完所有牌的策略 inline LL rush(int *xAtk, int *yAtk, int *yDef) { LL ret = 0; sort(xAtk + 1, xAtk + m + 1); sort(yDef + 1, yDef + totDef + 1); sort(yAtk + 1, yAtk + totAtk + 1); //先进行排序，然后找出与DEF相近的牌打 for(register int i = 1; i <= totDef; ++i) { int P = upper_bound(xAtk + 1, xAtk + m + 1, yDef[i]) - xAtk; if(xAtk[P] < yDef[i]) return 0; //如果连DEF都还不能打完，那么这种策略收益为0 xAtk[P] = -1; yDef[i] = -1; } sort(xAtk + 1, xAtk + m + 1); //注意这里要重新排序!数组的值发生了变化 for(register int i = 1; i <= totAtk; ++i) { int P = lower_bound(xAtk + 1, xAtk + m + 1, yAtk[i]) - xAtk; if(xAtk[P] < yAtk[i] || xAtk[P] == -1 || yAtk[i] == -1) return ret; //如果打不动ATK了，只能删库带着收益跑路了 ret += xAtk[P] - yAtk[i]; xAtk[P] = -1; yAtk[i] = -1; } for(register int i = 1; i <= m; ++i) if(xAtk[i] != -1) ret += xAtk[i]; //康康还有没有真伤qwq return ret; } //策略二，把大牌直接炸出去 inline LL blow(int *xAtk, int *yAtk, int *yDef) { LL ret = 0; sort(xAtk + 1, xAtk + m + 1); sort(yAtk + 1, yAtk + totAtk + 1); //这里的变量条件的意思是 //如果我的牌还没打完，就继续循环 //因为可能还有DEF，所以这里不累计真伤 //对方牌值-1就是没ATK牌了 for(register int i = m, j = 1; i >= 1; --i, ++j) if(xAtk[i] >= yAtk[j]) { if(yAtk[j] != -1) { ret += xAtk[i] - yAtk[j]; xAtk[i] = -1; yAtk[j] = -1; } } return ret; } signed main() { scanf("%d%d", &n, &m); char str[7]; //设初值 memset(xAtk, -1, sizeof(xAtk)); memset(yAtk, -1, sizeof(yAtk)); memset(yDef, -1, sizeof(yDef)); memset(copy_xAtk, -1, sizeof(copy_xAtk)); memset(copy_yAtk, -1, sizeof(copy_yAtk)); memset(copy_yDef, -1, sizeof(copy_yDef)); for(register int i = 1; i <= n; ++i) { scanf("%s", str); if(str[0] == 'A') { ++totAtk; scanf("%d", &yAtk[totAtk]); } else { ++totDef; scanf("%d", &yDef[totDef]); } } for(register int i = 1; i <= m; ++i) scanf("%d", &xAtk[i]), copy_xAtk[i] = xAtk[i]; for(register int i = 1; i <= totAtk; ++i) copy_yAtk[i] = yAtk[i]; for(register int i = 1; i <= totDef; ++i) copy_yDef[i] = yDef[i]; printf("%lld", max( rush(xAtk, yAtk, yDef), blow(copy_xAtk, copy_yAtk, copy_yDef) )); //两种策略择优输出。 return 0; } ```