题目大意

这道题目难处理的是我方的牌可以打完,也可以不打完,并且由样例二可以发现并不是出数值相近的牌就能赢,很像是 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 :

#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;
}