题目链接

https://ac.nowcoder.com/acm/contest/8564/A

解题思路

大致思路：
建立结构体保存每个基地的防御力和价值，按照防御力从小到大排序（价值大小无所谓）；
再遍历排完序的基地结构体数组，保存小于等于当前遍历到的基地的防御力的最大价值；
遍历飞机的攻击力数组，二分找到防御力小于当前遍历到的飞机攻击力的基地，加上保存在最大价值数组中的值；
输出答案。
详细思路：
见代码注释

AC代码

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

const int N=1e6+100;

int a[N],d[N],v,n,m,mx[N],pos;
ll ans;
struct node
{
    int d,v;    
}bb[N];

bool cmp(node a,node b)
{
    return a.d<b.d;//价值无所谓，只要排防御力就行
}

int new_lower_bound(int x)//y总板子
{
    int l=0,r=m;
    while(l<r)
    {
        int mid=l+r+1>>1;//加1防止出现死循环
        if(bb[mid].d<x) l=mid;
        else r=mid-1;
    }
    return r;
}

int main()
{
    cin>>n>>m;
    bb[0].d=0;bb[0].v=0;//多插一组，防止出现飞机中的最小攻击力比基地最小防御力还小的情况
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>d[i];
    for(int i=1;i<=m;i++)
    {
        cin>>v;
        bb[i].d=d[i];
        bb[i].v=v;
    } 
    sort(bb+1,bb+m+1,cmp);
    for(int i=1;i<=m;i++)
    mx[i]=max(mx[i-1],bb[i].v);//mx数组用于保存排完序后，前i个基地（含第i个）的最大价值

    for(int i=1;i<=n;i++)
    {
        pos=new_lower_bound(a[i]);//我们找到的其实是小于a[i]且最大的位置（举例：01112，对应的下标从1开始，假如当前a[i]=2，我们通过newlowerbound函数返回的其实第三个1的位置，即下标为4）
        ans+=mx[pos];//让答案加上小于等于pos位置的最大价值（在pos位置及之前的位置的基地的防御力一定比当前飞机的攻击力小）
    }
    cout<<ans<<endl;
}