20191105 csp
T1 盘王节（panwang）
（WOJ4793）
【题目背景】
小 Q Q Q同学的家乡是远近闻名的瑶族文化旅游村， 村里最近正在开展传统节日特色活动。为了下届族长选举, 小 Q Q Q正想方设法地拉动自己的导游业绩。这次他拉来了他在月亮中学的同学小 L L L为了传播瑶族文化，你需要和小 L L L一起了解瑶族传统节日知识。
【题目描述】
盘王节是祭祀瑶族祖先盘古王的重大节日。
小L望着眼前的小 Q Q Q穿着盛装，鼓声镲声交错耳边，远古而悠长的音节从小 Q Q Q的口中淌出，仿佛构筑起一条现世与始祖神灵的通路。身旁的舞龙队伍盛大地游行着，小 Q Q Q的一双手突然拉住了小 L L L，他们融进了欢庆的人群中兴奋地共舞，夜空之下烟火绽开，华光渲染了他俩的眼眸，更照亮了少年内心暗暗涌动的情愫……
节日庆典上，小 Q Q Q向小 L L L介绍了一种特色双人益智游戏，以下为游戏的大体内容：
• 双方分为进攻方与防守方。
• 进攻方有 n n n种不同的兵符, 第i 种能力值为 a i a_i ai，各有 x i x_i xi个。
• 防守方有 m 1 m1 m1种不同的先灵庇佑的御符,，第 i i i种能力值为 b i b_i bi, 各有 y i y_i yi个。
• 防守方还有 m 2 m2 m2种不同的兵符，第 i i i种能力值为 c i c_i ci各有 z i z_i zi个。
这个游戏由进攻方主动, 每次可以选择一个兵符击破防守方的任意一个御符或任意一个兵符。
- 若进攻御符，不会对对方造成伤害，但如果能力值不低于对方，则可以破除对方这个符咒。
- 若进攻兵符，会对对方造成为两者能力值差的伤害，如果能力值不低于对方, 则可以破除对方这个符咒。
注意：
• 自己的符咒是消耗品，每个只能用一次。
• 如果自己的符能力值小于对方，视作无效操作且也会浪费当前符咒。
• 当对方所有御符都被破除后，自己还剩下的兵符可以越过对方兵符直接对对方造成能力值的伤害。
你需要最大化进攻方对防守方的伤害。
【输入格式】
从文件panwang.in中读入数据。
第一行三个整数, 表示 n , m 1 , m 2 n, m1, m2 n,m1,m2。
接下来 n n n行, 一行分别给出 a i , x i a_i, x_i ai,xi。
接下来 m 1 m1 m1行, 一行分别给出 b i , y i b_i, y_i bi,yi。
接下来 m 2 m2 m2行, 一行分别给出 c i , z i c_i, z_i ci,zi。
【输出格式】
输出到文件panwang.out中。
一行一个整数, 表示最大伤害
【样例1输入】
3 1 3
15 1
64 1
18 1
9 1
61 1
86 1
57 1
【样例1输出】
82
【样例1解释】
最优策略为：选择一号兵符破除对方御符后，二三号直接对对方造成伤害。
【样例2~3】
见选手目录下的panwang/panwang2 ~ 3.in与panwang/panwang2 ~ 3.ans。
【数据规模与约定】
对于所有数据， n ≤ 1 0 6 , m 1 ≤ 1 0 6 , m 2 ≤ 1 0 6 n\le 10^6,m1\le 10^6,m2\le 10^6 n≤106,m1≤106,m2≤106，所有能力值为绝对值小于等于 100 100 100的整数，单个种类的符咒数量不超过 1 0 9 10^9 109。
思路：
发现有两种方式可使伤害最大化。
- 只打兵符。
- 打御符和能使答案更优的兵符
一、只打兵符:
用自己手上最大的兵符打敌人手上最小的兵符，直到对 a n s ans ans没有贡献为止（即 v a l [ m i n e ] = = v a l [ e m e n y ] val[mine]==val[emeny] val[mine]==val[emeny]），使答案最优。
证明：
a n s ans ans即为 ∑ v a l [ m i n e ] − ∑ v a l [ e m e n y ] \sum val[mine]-\sum val[emeny] ∑val[mine]−∑val[emeny]。发现当 v a l [ m i n e ] < v a l [ e m e n y ] val[mine]\lt val[emeny] val[mine]<val[emeny]时，对答案的贡献为负。
二、打御符和能使答案更优的兵符
首先必将敌人手上的御符打完，不然打御符没有意义， a n s ans ans必定没有方案一优。其次用自己手上能打掉敌人御符的最小兵符打（简单贪心）。最后发现打敌人手上权值为负的兵符比直接打脸优。
实现：
敌人御符打完后，将敌人兵符中插入一个权值为零，数量 I N F INF INF的兵符，再按照方案一操作即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define in Read()
#define int long longint in{int s=0,f=1;char x;for(x=getchar();!isdigit(x);x=getchar()) if(x=='-') f=-1;for( ;isdigit(x);x=getchar()) s=(s<<1)+(s<<3)+(x&15);return s*f;
}const int A=5e6+5;
const int INF=1e18;
int n,m1,m2;
struct Fu{int val,num;inline friend bool operator < (const Fu &x,const Fu &y){if(x.val!=y.val) return x.val<y.val;return x.num<y.num;}
}ff[A],f1[A],f2[A],u[A],v[A];
int ans1,ans2,ans;inline void fight1(){if(ff[n].val<f1[m1].val) return;memcpy(u,ff,sizeof(ff));memcpy(v,f1,sizeof(f1));int p=1;for(int i=1;i<=n;i++){if(p>m1) break;while(u[i].val>=v[p].val&&u[i].num>0&&p<=m1){if(u[i].num>=v[p].num){u[i].num-=v[p].num;v[p].num=0;p++;}if(u[i].num<v[p].num){v[p].num-=u[i].num;u[i].num=0;}}}if(p<=m1) return;for(int i=1;i<=m2;i++){if(f2[i].val<0) v[i]=f2[i];else{v[i].val=0,v[i].num=INF;break;}}v[m2+1].val=0,v[m2+1].num=INF;p=1;for(int i=n;i>0;i--){if(u[i].val<=v[p].val) break;while(u[i].val>v[p].val&&u[i].num>0){if(u[i].num>=v[p].num){ans1+=(u[i].val-v[p].val)*v[p].num;u[i].num-=v[p].num;v[p].num=0;p++;}if(u[i].num<v[p].num){ans1+=(u[i].val-v[p].val)*u[i].num;v[p].num-=u[i].num;u[i].num=0;}}}return;
}inline void fight2(){memcpy(u,ff,sizeof(ff));memcpy(v,f2,sizeof(f2));int p=1;for(int i=n;i>0;i--){if(u[i].val<=v[p].val) break;if(p>m2) break;while(u[i].val>v[p].val&&u[i].num>0&&p<=m2){if(u[i].num>=v[p].num){ans2+=(u[i].val-v[p].val)*v[p].num;u[i].num-=v[p].num;v[p].num=0;p++;}if(u[i].num<v[p].num){ans2+=(u[i].val-v[p].val)*u[i].num;v[p].num-=u[i].num;u[i].num=0;}}}return;
}signed main(){n=in,m1=in,m2=in;for(int i=1;i<=n;i++)ff[i].val=in,ff[i].num=in;for(int i=1;i<=m1;i++)f1[i].val=in,f1[i].num=in;for(int i=1;i<=m2;i++)f2[i].val=in,f2[i].num=in;sort(ff+1,ff+1+n);sort(f1+1,f1+1+m1);sort(f2+1,f2+1+m2);fight1();fight2();ans=max(ans1,ans2);printf("%lld",ans);return 0;
}
20191105 csp
T1 盘王节（panwang）
（WOJ4793）
【题目背景】
小 Q Q Q同学的家乡是远近闻名的瑶族文化旅游村， 村里最近正在开展传统节日特色活动。为了下届族长选举, 小 Q Q Q正想方设法地拉动自己的导游业绩。这次他拉来了他在月亮中学的同学小 L L L为了传播瑶族文化，你需要和小 L L L一起了解瑶族传统节日知识。
【题目描述】
盘王节是祭祀瑶族祖先盘古王的重大节日。
小L望着眼前的小 Q Q Q穿着盛装，鼓声镲声交错耳边，远古而悠长的音节从小 Q Q Q的口中淌出，仿佛构筑起一条现世与始祖神灵的通路。身旁的舞龙队伍盛大地游行着，小 Q Q Q的一双手突然拉住了小 L L L，他们融进了欢庆的人群中兴奋地共舞，夜空之下烟火绽开，华光渲染了他俩的眼眸，更照亮了少年内心暗暗涌动的情愫……
节日庆典上，小 Q Q Q向小 L L L介绍了一种特色双人益智游戏，以下为游戏的大体内容：
• 双方分为进攻方与防守方。
• 进攻方有 n n n种不同的兵符, 第i 种能力值为 a i a_i ai，各有 x i x_i xi个。
• 防守方有 m 1 m1 m1种不同的先灵庇佑的御符,，第 i i i种能力值为 b i b_i bi, 各有 y i y_i yi个。
• 防守方还有 m 2 m2 m2种不同的兵符，第 i i i种能力值为 c i c_i ci各有 z i z_i zi个。
这个游戏由进攻方主动, 每次可以选择一个兵符击破防守方的任意一个御符或任意一个兵符。
- 若进攻御符，不会对对方造成伤害，但如果能力值不低于对方，则可以破除对方这个符咒。
- 若进攻兵符，会对对方造成为两者能力值差的伤害，如果能力值不低于对方, 则可以破除对方这个符咒。
注意：
• 自己的符咒是消耗品，每个只能用一次。
• 如果自己的符能力值小于对方，视作无效操作且也会浪费当前符咒。
• 当对方所有御符都被破除后，自己还剩下的兵符可以越过对方兵符直接对对方造成能力值的伤害。
你需要最大化进攻方对防守方的伤害。
【输入格式】
从文件panwang.in中读入数据。
第一行三个整数, 表示 n , m 1 , m 2 n, m1, m2 n,m1,m2。
接下来 n n n行, 一行分别给出 a i , x i a_i, x_i ai,xi。
接下来 m 1 m1 m1行, 一行分别给出 b i , y i b_i, y_i bi,yi。
接下来 m 2 m2 m2行, 一行分别给出 c i , z i c_i, z_i ci,zi。
【输出格式】
输出到文件panwang.out中。
一行一个整数, 表示最大伤害
【样例1输入】
3 1 3
15 1
64 1
18 1
9 1
61 1
86 1
57 1
【样例1输出】
82
【样例1解释】
最优策略为：选择一号兵符破除对方御符后，二三号直接对对方造成伤害。
【样例2~3】
见选手目录下的panwang/panwang2 ~ 3.in与panwang/panwang2 ~ 3.ans。
【数据规模与约定】
对于所有数据， n ≤ 1 0 6 , m 1 ≤ 1 0 6 , m 2 ≤ 1 0 6 n\le 10^6,m1\le 10^6,m2\le 10^6 n≤106,m1≤106,m2≤106，所有能力值为绝对值小于等于 100 100 100的整数，单个种类的符咒数量不超过 1 0 9 10^9 109。
思路：
发现有两种方式可使伤害最大化。
- 只打兵符。
- 打御符和能使答案更优的兵符
一、只打兵符:
用自己手上最大的兵符打敌人手上最小的兵符，直到对 a n s ans ans没有贡献为止（即 v a l [ m i n e ] = = v a l [ e m e n y ] val[mine]==val[emeny] val[mine]==val[emeny]），使答案最优。
证明：
a n s ans ans即为 ∑ v a l [ m i n e ] − ∑ v a l [ e m e n y ] \sum val[mine]-\sum val[emeny] ∑val[mine]−∑val[emeny]。发现当 v a l [ m i n e ] < v a l [ e m e n y ] val[mine]\lt val[emeny] val[mine]<val[emeny]时，对答案的贡献为负。
二、打御符和能使答案更优的兵符
首先必将敌人手上的御符打完，不然打御符没有意义， a n s ans ans必定没有方案一优。其次用自己手上能打掉敌人御符的最小兵符打（简单贪心）。最后发现打敌人手上权值为负的兵符比直接打脸优。
实现：
敌人御符打完后，将敌人兵符中插入一个权值为零，数量 I N F INF INF的兵符，再按照方案一操作即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define in Read()
#define int long longint in{int s=0,f=1;char x;for(x=getchar();!isdigit(x);x=getchar()) if(x=='-') f=-1;for( ;isdigit(x);x=getchar()) s=(s<<1)+(s<<3)+(x&15);return s*f;
}const int A=5e6+5;
const int INF=1e18;
int n,m1,m2;
struct Fu{int val,num;inline friend bool operator < (const Fu &x,const Fu &y){if(x.val!=y.val) return x.val<y.val;return x.num<y.num;}
}ff[A],f1[A],f2[A],u[A],v[A];
int ans1,ans2,ans;inline void fight1(){if(ff[n].val<f1[m1].val) return;memcpy(u,ff,sizeof(ff));memcpy(v,f1,sizeof(f1));int p=1;for(int i=1;i<=n;i++){if(p>m1) break;while(u[i].val>=v[p].val&&u[i].num>0&&p<=m1){if(u[i].num>=v[p].num){u[i].num-=v[p].num;v[p].num=0;p++;}if(u[i].num<v[p].num){v[p].num-=u[i].num;u[i].num=0;}}}if(p<=m1) return;for(int i=1;i<=m2;i++){if(f2[i].val<0) v[i]=f2[i];else{v[i].val=0,v[i].num=INF;break;}}v[m2+1].val=0,v[m2+1].num=INF;p=1;for(int i=n;i>0;i--){if(u[i].val<=v[p].val) break;while(u[i].val>v[p].val&&u[i].num>0){if(u[i].num>=v[p].num){ans1+=(u[i].val-v[p].val)*v[p].num;u[i].num-=v[p].num;v[p].num=0;p++;}if(u[i].num<v[p].num){ans1+=(u[i].val-v[p].val)*u[i].num;v[p].num-=u[i].num;u[i].num=0;}}}return;
}inline void fight2(){memcpy(u,ff,sizeof(ff));memcpy(v,f2,sizeof(f2));int p=1;for(int i=n;i>0;i--){if(u[i].val<=v[p].val) break;if(p>m2) break;while(u[i].val>v[p].val&&u[i].num>0&&p<=m2){if(u[i].num>=v[p].num){ans2+=(u[i].val-v[p].val)*v[p].num;u[i].num-=v[p].num;v[p].num=0;p++;}if(u[i].num<v[p].num){ans2+=(u[i].val-v[p].val)*u[i].num;v[p].num-=u[i].num;u[i].num=0;}}}return;
}signed main(){n=in,m1=in,m2=in;for(int i=1;i<=n;i++)ff[i].val=in,ff[i].num=in;for(int i=1;i<=m1;i++)f1[i].val=in,f1[i].num=in;for(int i=1;i<=m2;i++)f2[i].val=in,f2[i].num=in;sort(ff+1,ff+1+n);sort(f1+1,f1+1+m1);sort(f2+1,f2+1+m2);fight1();fight2();ans=max(ans1,ans2);printf("%lld",ans);return 0;
}