题解 P6851 【onu】

· · 题解

题解 P6851 【onu】

P6851 onu

这道题是一道很典型的贪心的题目。

首先小 D 每一次出牌都会买等于自己牌面的糖果数

其次赢了还可以多拿到 c 个糖果 ， 输了就失去 c 个糖果。

所以要赢，同时要赢得大。

这里就很像田忌赛马了。用自己小的和别人大的比，用大的去赢别人。

但这多一个颜色，就在排序贪心是，优先颜色（从小到大），其次牌面（从大到小）

操作时，先赢后输，先把能赢得都赢了，再考虑怎么输：

inline void win()
{
    int i = 1,j = 1;
    for (; i <= n; ++i)
    {
        if (put[i]) continue;
        while (C[j].color < D[i].color && j <= m) ++j; // 调整颜色至两张牌颜色统一
        for (;j <= m && D[i].color == C[j].color; ++j)
        {
            if (vis[j]) continue;// 如果这张牌用过了就跳过
            if (D[i].num >= C[j].num) //能赢的最大的牌，赢掉这张，最大降低对方牌面大小
            {
                put[i] = vis[j] = true;
                sum += (D[i].num + each);
                ans[C[j].indax] = D[i].indax;
                break;
            }
        }
    }
    return ;
}

然后考虑输的情况，大大牌肯定是要出的，小牌可以不出，

如果，小 D 的牌少，就输出 -1 ，所以

inline void lose()
{
    int i = 1,j = 1;
    for (; i <= n; ++i)
    {
        if (put[i]) continue;
        while (C[j].color < D[i].color && j <= m) ++j;
        for (;j <= m && D[i].color == C[j].color; ++j)
        {
            if (vis[j]) continue;
            sum += (D[i].num - each);
            put[i] = vis[j] = true;
            ans[C[j].indax] = D[i].indax;
            break;
        }
    }
    for (int x = 1; x <= m; ++x)
    {
        if (vis[x]) continue;
        sum -= each;
    }
    return ;
}

code

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int SIZE = 1e5 + 50;

inline int read()
{
    int x = 0,f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        f = (ch == '-' ? -1 : 1);
        ch =  getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return f * x;
}

int n,m,each,sum;
int color[SIZE],ans[SIZE];
bool vis[SIZE],put[SIZE];
struct onu
{
    int color,num,indax;
};
onu C[SIZE],D[SIZE];

inline bool cmp(onu a,onu b) 
{
    return (a.color == b.color ? (a.num == b.num ? a.indax < b.indax : a.num > b.num) : a.color < b.color);
}

inline void get()
{
    memset(ans,-1,sizeof(ans));
    n = read();m = read();each = read();sum = read();
    for (int i = 1; i <= n; ++i)
    {
        D[i].color = read();D[i].num = read();D[i].indax = i;
    }
    for (int i = 1; i <= m; ++i)
    {

        C[i].color = read();C[i].num = read();C[i].indax = i;
    }
    sort(C+1,C+1+m,cmp);sort(D+1,D+1+n,cmp);
}

inline void win()
{
    int i = 1,j = 1;
    for (; i <= n; ++i)
    {
        if (put[i]) continue;
        while (C[j].color < D[i].color && j <= m) ++j;
        for (;j <= m && D[i].color == C[j].color; ++j)
        {
            if (vis[j]) continue;
            if (D[i].num >= C[j].num)
            {
                put[i] = vis[j] = true;
                sum += (D[i].num + each);
                ans[C[j].indax] = D[i].indax;
                break;
            }
        }
    //  cout << D[i].indax << " " << D[i].num << " " << each << " " << sum << endl;
    }
    return ;
}

inline void lose()
{
    int i = 1,j = 1;
    for (; i <= n; ++i)
    {
        if (put[i]) continue;
        while (C[j].color < D[i].color && j <= m) ++j;
        for (;j <= m && D[i].color == C[j].color; ++j)
        {
            if (vis[j]) continue;
            sum += (D[i].num - each);
            put[i] = vis[j] = true;
            ans[C[j].indax] = D[i].indax;
            break;
        }
    //  cout << D[i].indax << " " << D[i].num << " " << each << " " << sum << endl;
    }
    for (int x = 1; x <= m; ++x)
    {
        if (vis[x]) continue;
        sum -= each;
    }
    return ;
}

inline void output()
{
    printf("%lld\n",sum);
    for (int i = 1; i <= m; ++i)
    {
        printf("%lld\n",ans[i]);
    }
    return ;
}

inline void solve()
{
    win();
    lose();
    return ;
}

signed main()
{
    get();
    solve();
    output();
    return 0;
}