【多校联考2020】盘王节-题解

题意描述

盘王节是祭祀瑶族祖先盘古王的重大节日.

小 L 望着眼前的小 Q 穿着盛装, 鼓声镲声交错耳边, 远古而悠长的音节从小 Q 的口中淌出, 仿佛构筑起一条现世与始祖神灵的通路. 身旁的舞龙队伍盛大地游行着, 小 Q 的一双手突然拉住了小 L, 他们融进了欢庆的人群中兴奋地共舞, 夜空之下烟火绽开, 华光渲染了他俩的眼眸, 更照亮了少年内心暗暗涌动的情愫…

节日庆典上, 小 Q 向小 L 介绍了一种特色双人益智游戏, 以下为游戏的大体内容:

• 双方分为进攻方与防守方.
• 进攻方有 $n$ 种不同的兵符, 第 $i$ 种能力值为 $a_i$, 各有 $x_i$ 个.
• 防守方有 $m_1$ 种不同的先灵庇佑的御符 , 第 $i$ 种能力值为 $b_i$, 各有 $y_i$ 个.
• 防守方还有 $m_2$ 种不同的兵符 , 第 $i$ 种能力值为 $c_i$, 各有 $z_i$ 个.

这个游戏由进攻方主动, 每次可以选择一个兵符击破防守方的任意一个御符或任意一个兵符.

1. 若进攻御符, 不会对对方造成伤害, 但如果能力值不低于对方, 则可以破除对方这个符咒。
2. 若进攻兵符, 会对对方造成为两者能力值差的伤害, 如果能力值不低于对方, 则可以破除对方这个符咒

注意：

• 自己的符咒是消耗品, 每个只能用一次
• 如果自己的符能力值没有对方高, 视作无效操作. 且也会浪费当前符咒.
• 当对方所有御符都被破除后, 自己还剩下的兵符可以越过对方兵符, 直接对对方造成能力值的伤害.

你需要最大化进攻方对防守方的伤害。

---

输入格式

从文件 panwang.in 中读入数据。

第一行三个整数, 表示 $n, m1, m2$

接下来 $n$ 行, 每一行分别给出 $a_i, x_i$

接下来 $m_1$ 行, 每一行分别给出 $b_i, y_i$

接下来 $m_2$ 行, 每一行分别给出 $c_i, z_i$

---

输出格式

输出到文件 panwang.out 中。

一行一个整数, 表示最大伤害

---

Input & Output ‘s examples

Input ‘s eg

3 1 3
15 1
64 1
18 1
9 1
61 1
86 1
57 1

Output ‘s eg

82

---

数据范围与约定

测试点编号	$n,m \leq$	$\sum x_i + y_i + z_i \leq$
$1 \to 4$	$5$	$15$
$5 \to 10$	$1000$	$6000$
$11 \to 14$	$10^6$	$6 \times 10^6$
$15 \to 20$	$10^6$	无特殊限制

对于所有数据, $1 \leq n ≤ 10^6; 1 \leq m1 , m2 ≤ 10^6$, 所有能力值为绝对值 小于 $100$ 的整数,单个种类的符咒数量不超过 $10^9$

---

分析

看到题目给出一个双人游戏自然会向贪心或博弈上想，而这题只提到了进攻方，故八成是贪心。

读完题目，不难发现只有两种情况可能是最优解。分别是打目前能打的最小兵符一直打到没有收益为止 与 打破所有盾之后去打脸

其中第一个情况直接用大的打对方小的即可。

对于第二种情况，我们需要尽量用能力值小的兵去击破对方的盾，则我们将对方的盾和自己的兵从大到小排序，之后选择刚好比对方能力值大的兵去打即可。

对方的盾全部击破之后就相当于其多了个能力值为 $0$，数目为无限的兵，然后就变成了第一种情况。

但要注意，题目中可能存在能力值小于 $0$ 的兵，此时打这个兵是比直接打脸要更优的，处理时候注意一下即可。

剩下的就是细节问题了，直接参考代码吧。

以及不要乱用 j1 , j2 一类的字母作为变量名(来自考场上用了 j1 而爆零的笔者)

---

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 1000000 + 5;
const int HA = 998244353;

//两种打法：一直打最小的兵或者破掉所有盾之后打max(最小的兵,胡脸)

ll n , m1 , m2;

struct Jian{
    ll bru , num;
}J1[M] , J2[M];

struct Dun{
    ll bru , num;
}d[M];

bool cmp1(Jian a , Jian b) {
    if(a.bru == b.bru) return a.num < b.num;
    else return a.bru < b.bru;
    
}
bool cmp2(Dun a , Dun b) { 
    if(a.bru == b.bru) return a.num < b.num;
    else return a.bru < b.bru;
}


Jian a[M] , b[M];
Dun c[M];

ll ans1;

// J1 为进攻方的兵，J2 为防守方的兵，d 为防守方的盾

void solve1() {
    copy(a , J1) , copy(b , J2);
    
    int pla = 1;
    per(i , n , 0){
        if(a[i].bru <= b[pla].bru) break;
        if(pla > m2) break;
        
        while(a[i].bru > b[pla].bru && a[i].num > 0 && pla <= m2){
            if(a[i].num >= b[pla].num){
                ll val = a[i].bru - b[pla].bru;
                val *= b[pla].num;
                ans1 += val;
                a[i].num -= b[pla].num , b[pla].num = 0;
                pla ++;
            }
            else {
                ll val = a[i].bru - b[pla].bru;
                val *= a[i].num;
                ans1 += val;
                b[pla].num -= a[i].num;
                a[i].num = 0;
            }
        }
        
    }
}

// J1 为进攻方的兵，J2 为防守方的兵，d 为防守方的盾

ll ans2;

void solve2() {
    copy(a , J1) , copy(b , J2) , copy(c , d);
    
    int pla = 1;
    rep(i , 1 , n){
        if(pla > m1) break;
        
        while(a[i].bru >= c[pla].bru && a[i].num > 0 && pla <= m1){
            if(a[i].num >= c[pla].num){
                a[i].num -= c[pla].num;
                c[pla].num = 0;
                pla ++;
            }
            else {
                c[pla].num -= a[i].num;
                a[i].num = 0;
            }
        }
    }
    
    if(pla <= m1) return ;
    
    rep(i , 1 , m2){
        if(b[i].bru < 0) continue;
        else {
            b[i].bru = 0 , b[i].num = 0x3f3f3f3f;
        }
    }
    b[m2 + 1].bru = 0 , b[m2 + 1].num = 0x3f3f3f3f;
    
    pla = 1;
    per(i , n , 1){
        if(a[i].bru <= b[pla].bru) break;
    
        while(a[i].bru > b[pla].bru && a[i].num > 0) {
            if(a[i].num >= b[pla].num){
                ll val = a[i].bru - b[pla].bru;
                val *= b[pla].num;
                ans2 += val;
                a[i].num -= b[pla].num;
                b[pla].num = 0;
                pla ++;
            }
            else {
                ll val = a[i].bru - b[pla].bru;
                val *= a[i].num;
                ans2 += val;
                b[pla].num -= a[i].num;
                a[i].num = 0;
            }
        }
    }
}

#define LOCAL

int main() {
    #ifdef LOCAL
        freopen("panwang.in" , "r" , stdin);
        freopen("panwang.out" , "w" , stdout);
    #endif
    read(n) , read(m1) , read(m2);
    rep(i , 1 , n) read(J1[i].bru) , read(J1[i].num);
    rep(i , 1 , m1) read(d[i].bru) , read(d[i].num);
    rep(i , 1 , m2) read(J2[i].bru) , read(J2[i].num);
    
    sort(J1 + 1 , J1 + 1 + n , cmp1);
    sort(J2 + 1 , J2 + 1 + m2 , cmp1);
    sort(d + 1 , d + 1 + m1 , cmp2);
    
    solve1() , solve2();
    
    printf("%lld\n" , max(ans1 , ans2));


    return 0;
}

---

THE END