題目鏈接
題目描述
Strength gives you the confidence within yourself to overcome any fears, challenges or doubts. Feel the fear and do it anyway! If you have been going through a rough time and feel burnt out or stressed, the Strength card encourages you to find the strength within yourself and keep going. You have got what it takes to see this situation through to its eventual end. You might also feel compelled to hold space for someone else who is going through a difficult period and needs your strength and support.
Alice and Bob are playing ``Yu-Gi-Oh!'', a famous turn-based trading card game, in which two players perform their turns alternatively. After several turns, Alice and Bob have many monsters respectively. Alice has n and Bob has m monsters under their own control. Each monster's strength is measured by a non-negative integer si. To be specific, the larger si is, the more power the monster has.
During each turn, for every single monster under control, the player can give a command to it at most once, driving it to battle with an enemy monster (given that opposite player has no monsters as a shield, the monster can directly attack him).
Additionally, the process of the battle is also quite simple. When two monsters battle with each other, the stronger one (i.e. the one with larger si) will overwhelm the other and destroy it and the winner's strength will remain unchanged. Meanwhile, the difference of their strength will produce equivalent damage to the player who loses the battle. If the player is directly attacked by a monster, he will suffer from the damage equal to the monster's strength. Notice that when two monsters have the same strength, both of them will vanish and no damage will be dealt.
Right now it is Alice's turn to play, having known the strength of all monsters, she wants to calculate the maximal damage she can deal towards Bob in one turn. Unfortunately, Bob has great foresight and is well-prepared for the upcoming attack. Bob has converted several of his monsters into defense position, in which even if the monster is destroyed, he wouldn't get any damage.
Now you are informed of the strength of all the monsters and whether it is in defense position for each Bob's monster, you are expected to figure out the maximal damage that could be dealt in this turn.
輸入
The first line contains a single integer T≤20 indicating the number of test cases.
For each test case, the first line includes two integer O≤n,m≤100000, representing the number of monsters owned by Alice and Bob.
In next three lines, the first two lines include n and m integers O≤si≤109 indicating the strength of the i-th monster, separated by spaces. The last line contains m integers 0 or 1 indicating the position of Bob’Si-th monsters. In other words, 0 represents the normal position and 1 represents the defense position.
輸出
For the ith test, output a single line in beginning of ``Case i:'', followed by an integer indicating the answer, separated by a single space.
樣例輸入
2
4 2
10 10 10 20
5 15
0 1
4 2
10 10 10 20
5 25
0 1樣例輸出
Case 1: 25
Case 2: 15
題意
玩游戲王牌，我方場上n只怪獸，都是攻擊形態，戰斗力為a[i]；
敵方m只怪獸，戰斗力為b[i]，如果下一行是0表示攻擊形態，1表示防御形態
如果我方怪獸的戰斗力攻擊對方攻擊形態的怪獸，就會消滅對方的怪獸，并造成超殺（對敵人本體造成戰斗力的差值a[i] - b[i]的血量），如果攻擊防御形態的怪獸獸，則會消滅怪獸而不會扣對方本體的血量
如果敵人沒有怪獸了，就可以對敵人本體造成直接傷害a[i]；
每只怪獸只能攻擊一次
問怎么才能扣敵人最多的血
題解
有兩種貪心策略
一種是 直接拿戰斗力高的去懟敵人戰斗力低的攻擊形態怪，這樣造成的超殺值高
第二種 用戰斗力高的去消滅所有的防御怪和攻擊怪，然后直接對本體進行攻擊
分別求出兩種貪心策略的結果求max
代碼寫的相當繁瑣
代碼
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define scac(x) scanf("%c",&x)
#define sca(x) scanf("%d",&x)
#define sca2(x,y) scanf("%d%d",&x,&y)
#define sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define scl(x) scanf("%lld",&x)
#define scl2(x,y) scanf("%lld%lld",&x,&y)
#define scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define pri(x) printf("%d\n",x)
#define pri2(x,y) printf("%d %d\n",x,y)
#define pri3(x,y,z) printf("%d %d %d\n",x,y,z)
#define prl(x) printf("%lld\n",x)
#define prl2(x,y) printf("%lld %lld\n",x,y)
#define prl3(x,y,z) printf("%lld %lld %lld\n",x,y,z)
#define ll long long
#define LL long long
#define read read()
#define pb push_back
#define mp make_pair
#define P pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(1.0)
#define eps 1e-6
#define inf 1e17
#define INF 0x3f3f3f3f
#define N 205
const int maxn = 1e5+5;
ll a[maxn],b[maxn];
ll g[maxn];//gong
ll s[maxn];//shou
int vis[maxn];
int op;
bool cmp(ll x,ll y)
{return x > y;
}
int main()
{int t;sca(t);int kase = 0;while(t--){memset(vis,0,sizeof(vis));int n,m;sca2(n,m);rep(i,0,n) scl(a[i]);rep(i,0,m) scl(b[i]);int cntg = 0;int cnts = 0;rep(i,0,m){sca(op);if(op) s[cnts++] = b[i];else g[cntg++] = b[i];}sort(a,a+n,cmp); // da -> xiaosort(g,g+cntg); // xiao -> dasort(s,s+cnts,cmp); // da -> xiaoint posa = 0;int posg = 0;int poss = cnts-1;ll ans = -1;ll temp = 0;while(posa < n && posg < cntg) //plan1 先打攻擊怪{if(a[posa] >= g[posg]){temp += a[posa] - g[posg]; posa++;posg++;}elsebreak;}ll sum = 0;if(posg != cntg) //我方怪打完了，對方攻擊怪還有剩余{ans = max(ans, temp);}else{int i = n-1;while(i >= posa && poss >= 0)//開始打防守怪{if(a[i] >= s[poss]) {i--;poss--;}else{sum += a[i];i--;}}if(poss == -1) {temp += sum;if(i != posa){while(i>=posa){temp += a[i];i--;}}}ans = max(ans,temp);}posa = n-1;poss = cnts - 1;while(posa >= 0 && poss >= 0) //plan2 先打防守怪{if(a[posa] >= s[poss]){vis[posa] = 1;posa--;poss--;}else{posa--;}}if(poss == -1) {posa = 0;posg = cntg - 1;temp = 0;while(posa < n && posg >= 0) {if(vis[posa]) //前面拿來打防守怪了{posa++;continue;}if(a[posa] >= g[posg]) {temp += a[posa] - g[posg];posa++;posg--;}else{break;}}if(posg == -1) {while(posa < n){if(vis[posa]){posa++;continue;}temp += a[posa];posa++;}ans = max(ans,temp);}}printf("Case %d: %lld\n",++kase,ans);}return 0;}
)
開放下載！)
