题目链接：https://ac.nowcoder.com/acm/problem/213755

到主站看：https://blog.csdn.net/weixin_43346722/article/details/109884094

题目

scimoon 率领的反叛军已经做好了准备

他的手下有 个战机，每架战机有一个破坏力

帝国有 个基地，每个基地有一个防御值 ，基地有一个价值

若一个战机的攻击力严格大于基地的防御值，则可以破坏该基地，得到这个基地的价值

帝国的后备资源很多，一个基地可以被反复破坏

每架战机最多只能选择一个基地攻击，当然也可以不攻击

求能获得的最大贡献

输入

一行两个整数，

第二行 个整数，表示

第三行 个整数，表示

第四行 个整数，表示

意义与题目描述中一致

输出

一行一个整数，表示最大价值

样例输入

3 5
1 2 3
1 2 3 4 5
1 2 3 4 5

样例输出

3

数据范围

思路

这道题我用了二分。
（不过好像做复杂了）

先二分出最大能打防御值多大的基地，然后之前用维护得出最大能打防御值为多少的基地时，能打出的最大贡献是多少。

然后就每一个二分一次，把每个贡献加起来，就是答案。

代码

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

struct node {
    int d, v;
}b[1000001];
int n, m, ans, a[1000001], lef, righ, mid, an;

bool cmp(node x, node y) {
    if (x.d != y.d) return x.d < y.d;
    return x.v > y.v;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++) scanf("%d", &b[i].d);
    for (int i = 1; i <= m; i++) scanf("%d", &b[i].v);

    sort(b + 1, b + m + 1, cmp);
    for (int i = 1; i <= m; i++)
        b[i].v = max(b[i].v, b[i - 1].v);

    for (int i = 1; i <= n; i++) {
        lef = 1;
        righ = m;
        an = -1;
        while (lef <= righ) {//二分最大能打哪个
            mid = (lef + righ) / 2;
            if (a[i] > b[mid].d) lef = mid + 1, an = mid;
                else righ = mid - 1;
        }
        if (an != -1) ans += b[an].v;
    }

    printf("%d", ans);

    return 0;
}