P6851 onu 题解

这是一道贪心题，但细节较多，需要一一考虑。

题目要求的就是获得糖果数量的最大值，因而我们就必须要分析糖果从何而来。

如果小 D 不弃权，不妨设其出的牌点数为 $x$。那么在本题中，糖果的获取 / 失去方式有：

1. 初始糖果数量为 $v$

2. 小 D 与小 C 拼点后获胜，每次可以获得 $c+x$ 颗

3. 小 D 与小 C 拼点后失败，每次可以获得 $x-c$ 颗（即失去 $c+x$ 颗）

4. 小 D 选择弃权，每次可以获得 $-c$ 颗（即失去 $c$ 颗）

本题中，小 C 在拼点上有主动性。即若小 C 发起拼点，则小 D 必须回应。

举个极端的例子：如果小 D 有 $10^5$ 张同种花色的牌，而小 C 却在该花色下没有牌，那么即使小 D 有再多的这种牌，也无济于事。反之，如果小 C 有 $10^5$ 张同种花色的牌，而小 D 却在该花色下没有牌，那么他只能选择弃权（从而失去 $10^5c$ 颗糖果）。

因而，我们必须要利用好小 D 的牌来应对小 C。

在贪心的过程中，我们实际上只需要考虑情况 $2,3,4$。

对于小 D 来说，他只在卡牌的选择上有主动性。正是因为有了这个主动性，才有了本题。

从整体来看，小 D 应当尽量保证自己赢的次数更多，从而能够赚得更多的糖果（如果赢的次数少，那么输的糖果就多），即多执行情况 $2$。

而情况 $2$ 该以什么样的顺序执行也是一个问题。为了获得更多的糖果，就要让小 D 尽可能打大的牌（这样赢的糖多）。而大牌所选择的拼点对象也得考虑。例如，我们应当避免用小 D 的 $10^5$ 点和小 C 的 $1$ 点进行拼点，否则就失去了一个能够赢过小 C 更大点数牌的机会，也就失去了赢的机会。

因此，我们应当从大到小枚举小 D 牌的点数，然后从大到小寻找小 C 的牌，使得在小 D 能够获胜的情况下，小 C 的牌要尽可能大。

接下里考虑剩余的情况，也就是情况 $2$ 处理完之后还没有打出的牌。

在能赢都赢的情况下，对于小 C 的一张牌，如果我们选择弃权，就失去了糖果，而不弃权的话则还能获得一部分糖果。因此，在小 D 的牌的数量足够的情况下，应当尽量不选择弃权。而如果小 D 剩余的牌大于小 C 的，那么显然应当从大到小进行排序，这样获得的价值就最大。

分析完了之后，我们应当考虑如何编写出这道题的程序来。不妨默认所有的牌都弃权，那么小 D 初始糖果数量就等于 $v-c \times m$。同时建立输出结果的数组，将其全部初始化为 $-1$。这样有便于后续的处理。

对于每一种花色，我们建立一个线性表来分别存储小 D 和小 C 的牌型信息。然后按刚才的思路和顺序进行模拟即可。

C++ 代码：

#include<bits/stdc++.h>
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<10,stdin),p1==p2)?EOF:*p1++)
using namespace std;
int n,m,c,res[100001];//res 保存输出结果
long long v;//v 表示最多能获得糖果的数量（需要开 long long，否则只有 40 分）
char buf[1<<10],*p1=buf,*p2=buf;
struct node//建立结构体来存储每张牌的点数和 id 编号（即输入的顺序）
{
    int val,id;
    bool operator<(const node &a)const//按照点数大小从大到小排序
    {
        return val>a.val;
    }
};
vector<node>a[100001],b[100001];//可以用 vector 形式的线性表来存储两个人手牌的信息
bitset<100001>use;//标记小 D 的牌是否被打出
template<typename t>void read(t &x)
{
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
}
int read()
{
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x;
}
int main()
{
    memset(res,-1,sizeof(res));
    read(n),read(m),read(c),read(v);
    v-=1LL*c*m;//直接默认全弃权，减去 c*m
    for(int i=1;i<=n;i++)a[read()].push_back((node){read(),i});//在对应的花色容器中插入对应的牌型信息（点数和编号）
    for(int i=1;i<=m;i++)b[read()].push_back((node){read(),i});
    for(int k=1,ld,lc,lv;k<=1e5;k++)//在点数最小值和最大值之间枚举
    {
        vector<node>D=a[k],C=b[k];
        ld=D.size(),lc=C.size();
        if(!lc||!ld)continue;
        /*
        如果有一个序列为空就不再操作：
        1. 小 C 序列为空：小 D 无法选择拼点
        2. 小 D 序列为空：程序开头已经默认全部弃权
        */
        sort(D.begin(),D.end());
        sort(C.begin(),C.end());
        //将两个序列排序
        vector<int>vacant;//用来保存在卡牌的 vector 中，未被使用的卡牌编号
        use.reset();//bitset 重置
        for(int i=0,j=0;i<lc&&j<ld;i++)
        {
            if(D[j].val>=C[i].val)//判断小 D 是否能获胜
            {
                res[C[i].id]=D[j].id;
                v+=D[j].val+(c<<1);//前面默认弃权，所以还要多加一个 c
                use[j++]=true;//标记使用
            }
        }
        for(int i=0;i<ld;i++)if(!use[i])vacant.push_back(i);//将没有使用的插入 vector 中
        lv=vacant.size();
        for(int i=0,j=0;i<lc&&j<lv;i++)
        {
            if(res[C[i].id]==-1)
            {
                res[C[i].id]=D[vacant[j]].id;
                v+=D[vacant[j]].val;
                j++;
                //小 C 打出的牌之前弃权的话，可以在此处相应，选择拼点
            }
        }
    }
    printf("%lld\n",v);
    for(int i=1;i<=m;i++)printf("%d\n",res[i]);
    return 0;
}