Strength

　

strength

Strength

题意：你有n个怪物，敌方有m个怪物，你攻击对方攻击状态的怪物，对方会损伤两个怪物攻击值的差值的血量，当然你的怪物的攻击力肯定要大于对方的。攻击防御的则对方不受伤害，最后还剩多少怪物，他就直接承受他们的伤害，问怎样使得对方所受伤害最大。

贪心：两种情况，你能把所有的怪打死，选最少的花费去攻击防御怪，剩下的减去攻击怪即可，你不能把所有怪打死就每次选最大的打最小的攻击怪。

#include<bits/stdc++.h>
using namespace std;
struct node{
	int s,t;
}a[100005];
int b[100005];
int vis[100005];
int cmp(node x,node y){
	return x.s<y.s;
}
int main(){
	int T;
	scanf("%d",&T);
	for(int j=1;j<=T;j++){
		memset(vis,0,sizeof(vis));
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;i++)
			scanf("%d",&b[i]);
		for(int i=0;i<m;i++)
			scanf("%d",&a[i].s);
		for(int i=0;i<m;i++)
			scanf("%d",&a[i].t);
		sort(a,a+m,cmp);
		sort(b,b+n);
		long long ans1=0,ans2=0;
		int l=0,r=0;
		while(l<n&&r<m){
			if(b[l]>=a[r].s){
				if(a[r].t==0){
					ans1+=b[l]-a[r].s;
				}
				vis[l]=1;
				l++;
				r++;
			}
			else l++;
		}
		if(r==m){
			for(int i=0;i<n;i++)
				if(!vis[i])
					ans1+=b[i];
		}
		else{
			l=0,r=n-1;
			while(r>=0&&l<m){
				if(b[r]>=a[l].s&&a[l].t==0){
					ans2+=b[r]-a[l].s;
					r--;
					l++;
				}
				else l++;
			}
		}
		printf("Case %d: %lld\n",j,max(ans1,ans2));
	}
}

相关阅读