题解

贪心

对于每个房子按照舒适度排序从大到小排序，对于其价格 $x$，找到所有人中持有的金币第一个 $\ge x$ 的(用二分实现)，表示最适合买当前房子的人，并将其删去即可。

在cpp中动态删除和二分的过程可以用 multiset 来实现

整体时间复杂度: $O(n \log n)$

AC代码

• CPP

#include <bits/stdc++.h>

using namespace std;

#define int long long
signed main() {
    int n, m;
    cin >> n >> m;
    multiset<int> ms;
    for(int i = 0; i < n; i ++)
    {
    	int x; cin >> x;
    	ms.insert(x);
    }
    vector<array<int, 2>> h(m);
    for(auto&[l, r] : h) cin >> l >> r;
	sort(h.begin(), h.end(), greater<array<int, 2>>());
    int res = 0;
	for(auto& [l, r] : h)
	{
		auto ite = ms.lower_bound(r);
		if(ite != ms.end())
			res += l, ms.erase(ite);
	}
 	cout << res << "\n";
    return 0;
}

java

import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n =sc.nextInt(),m = sc.nextInt();
        int[] friend = new int[n];
        for(int i =0;i<n;i++) friend[i] = sc.nextInt();
        int[][] house = new int[m][2];
        for(int i=0;i<m;i++){
            for(int j=0;j<2;j++){
                house[i][j] = sc.nextInt();
            }
        }

        GetRes_(house,friend);

    }

    private static void GetRes_(int[][] house, int[] friend) {

        Arrays.sort(friend);
        Arrays.sort(house,(a,b)->a[1]-b[1]);

        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        long res=0;
        int index=0;
        for(int fri:friend){
            while(index< house.length && fri>=house[index][1]){
                queue.add(house[index][0]);
                index++;
            }
            res+=(queue.size()==0?0: queue.poll());
        }
        System.out.println(res);

    }
}

题目描述

小红有 $n$ 个朋友，每个朋友有一定数量的金币，现在他们要购买房子，一共有 $m$ 个房子，每个房子有两个参数：舒适度和价格，当一个人的金币大于等于一个房子的价格时，才可以购买房子，且要满足以下条件：

1. 一个人至多购买一个房子。
2. 一个房子至多被一个人购买。

现在小红想知道 $n$ 个朋友购买的房子的舒适度之和最大可能是多少？

输入描述

第一行两个整数 $n$ 和 $m$

接下来一行 $n$ 个数，第 $i$ 个整数 $x$ 表示第 $i$ 个人的金币 $x$， $1 \leq x \leq 10^9$

接下来 $m$ 行每行两个整数表示每个房子的舒适度 $a$ 和价格 $b$， $1 \leq a, b \leq 10^9$，$1 \leq n, m \leq 2 \times 10^5$

输出描述

输出一个数表示最大可能的舒适度之和。

示例 1

输入

2 2
2 2 
2 2
2 2

输出

4