题解 P2813 【母舰】
Rbu_nas
2018-10-18 18:12:40
题意描述：一艘舰M个防御系统，夕立有N发炮弹，打击完防御系统后可以对舰造成伤害，问你最大的伤害值。
贪心，没啥好说的，每次发射伤害离防御值最接近的导弹，注意下“炮弹伤害**大于防御系统**可以摧毁防御系统”就好了。
思路：首先对防御值与伤害值都进行排序，依次枚举防御值$Tex_i$，如果没有找到可以破坏其的导弹$Poi_i$，直接输出$0$。
寻找导弹这里采用的是$STL$炒鸡好用的`upper_bound`。
---
代码：
```cpp
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL; //为了防tot与ans炸随手long long.
const int N=100000+5;
LL Tex[N], Poi[N], tot_tex, tot_poi, ans; //Tex-防御值 Poi-导弹伤害值.
int main(int argc, char const *argv[])
{
int m, n; scanf("%d %d", &m, &n);
if(n < m) return printf("0")&0; //小优化,如果导弹数量比防御系统数量还少肯定咕咕.
for(register int i=1; i<=m; ++i) scanf("%lld", &Tex[i]), tot_tex+=Tex[i];
for(register int i=1; i<=n; ++i) scanf("%lld", &Poi[i]), tot_poi+=Poi[i];
if(tot_poi <= tot_tex) return printf("0")&0; //如果导弹总伤害值都不够打的也凉凉.
sort(Tex+1, Tex+m+1); sort(Poi+1, Poi+n+1); //排序,从小到大枚举防御值.
for(register int i=1; i<=m; ++i)
{
int Place=upper_bound(Poi+1, Poi+n+1, Tex[i])-Poi; //找出第一个大于防御值的导弹的位置.
if(Poi[Place] < Tex[i]) return printf("0")&0;
Poi[Place]=0;
}
for(register int i=1; i<=n; ++i) ans+=Poi[i]; //累加还没有发射的导弹伤害值.
printf("%lld", ans);
return 0;
}
```
---
最后求过+赞$\mathfrak{qwq}$
大家珂以做做[P2695 骑士的工作](https://www.luogu.org/problemnew/show/P2695)来练练手，思路完全一样