题意描述:一艘舰M个防御系统,夕立有N发炮弹,打击完防御系统后可以对舰造成伤害,问你最大的伤害值。

贪心,没啥好说的,每次发射伤害离防御值最接近的导弹,注意下“炮弹伤害大于防御系统可以摧毁防御系统”就好了。

思路:首先对防御值与伤害值都进行排序,依次枚举防御值 $Tex_i$ ,如果没有找到可以破坏其的导弹 $Poi_i$ ,直接输出 $0$ 。

寻找导弹这里采用的是 $STL$ 炒鸡好用的upper_bound


代码:

#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 骑士的工作来练练手,思路完全一样