题解 P2813 【母舰】

sjl40 · 2017-12-23 21:56:31 · 题解

/* 这道题目有几个关键点要知道:

一、每个攻击系统只能打一个防御系统，打完了就没了。

二、我方的攻击系统的攻击力或者是敌方的防御系统的防御力可能为0。

三、要用尽量小的打他的防御系统，因为大的要放后面打母舰。

下面进入程序部分。

*/

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int tf[10000000],wf[10000000];
int m,n,s,i,t;
int main()
{
 cin>>m>>n;//输入敌方的防御系统数量和我方的攻击系统数量
 for(i=1;i<=m;i++)scanf("%d",&tf[i]);//输入敌方的防御系统的防御力
 for(i=1;i<=n;i++)scanf("%d",&wf[i]);//输入我方的攻击系统的攻击力
 sort(tf+1,tf+1+m);//进行排序。（注意：这里要从小到大，否则就不能用尽量小的来打敌方的防御系统，留大的来打母舰。）
 sort(wf+1,wf+1+n);//进行排序。（注意：这里要从小到大，否则就不能用尽量小的来打敌方的防御系统，留大的来打母舰。）
 t=1;//定义敌方现有的,最小的防御系统的防御力
 for(i=1;i<=n;i++)
 {
  if(tf[t]==0)t++;//要特别注意这里！！！否则其实没有防御系统，程序也自动把他当成有0的防御力的防御系统。
  if(tf[t]<wf[i]&&tf[t]!=0){wf[i]=0;t++;}//再判断一下当前的攻击系统能打破敌方现有的,最小的防御系统。如果能就清0做标记，并且换下一个防御系统进行攻打。
 }
 if(t<=m){cout<<0;return 0;}//如果打不完防御系统就一点伤害都没有。
 for(i=1;i<=n;i++)s+=wf[i];//否则就是有伤害，把剩下的攻击系统的攻击力加起来，这些就是可以打到母舰的攻击系统。
 cout<<s;//输出最多能打多少伤害
}