笔试时间：2024年07月27日 提前批

历史笔试传送门：2023秋招笔试合集

第一题

题目：购房之旅

小强有n个朋友，每个朋友有一定数量的金币，现在他们要购买房子，一共有m个房子，每个房子有两个参数：舒适度和价格，当一个人的金币大于等于一个房子的价格时，才可以购买房子，且要满足以下条件：1.一个人至多购买一个房子。2.一个房子至多被一个人购买。现在小强想知道n个朋友购买的房子的舒适度之和最大可能是多少？

输入描述

第一行两个整数n,m

接下来一行n个数，第i个整数x表示第i个人的金币x, 1<=x<=10^9

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

输出描述

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

样例输入

2 2

2 2

2 2

2 2

样例输出

4

说明

每个朋友都会买一个舒适度为2的房子

参考题解

贪心，对于每一个人，购买舒适度尽可能大的，并且价格尽可能接近的 。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

// 定义房子结构
struct House {
long long comfort;
long long price;
};

// 比较函数，用于将房子按价格从高到低排序
bool compareHouse(const House &a, const House &b) {
    return a.comfort > b.comfort;
}

int main() {
    int n, m;
    cin >> n >> m;

    // 读取朋友的金币数量
    multiset<long long> friends;
    for (int i = 0; i < n; ++i) {
        long long gold;
        cin >> gold;
        friends.insert(gold);
    }

    // 读取房子的舒适度和价格
    vector<House> houses(m);
    for (int i = 0; i < m; ++i) {
        cin >> houses[i].comfort >> houses[i].price;
    }

    // 按照价格从高到低排序房子
    sort(houses.begin(), houses.end(), compareHouse);

    long long maxComfortSum = 0;

    // 处理每个房子
    for (const House &house : houses) {
        auto it = friends.lower_bound(house.price);
        if (it != friends.end()) {
            // 找到第一个不小于房子价格的金币数量
            maxComfortSum += house.comfort;
            // 从集合中删除这个金币数量
            friends.erase(it);
        }
    }

    // 输出最大舒适度之和
    cout << maxComfortSum << endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    
    // 定义房子类
    static class House {
        long comfort;
        long price;

        House(long comfort, long price) {
            this.comfort = comfort;
            this.price = price;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        // 读取朋友的金币数量
        TreeMap<Long, Integer> friends = new TreeMap<>();
        for (int i = 0; i < n; ++i) {
            long gold = scanner.nextLong();
            friends.put(gold, friends.getOrDefault(gold, 0) + 1);
        }

        // 读取房子的舒适度和价格
        List<House> houses = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            long comfort = scanner.nextLong();
            long price = scanner.nextLong();
            houses.add(new House(comfort, price));
        }

        // 按照价格从高到低排序房子
        houses.sort((a, b) -> Long.compare(b.price, a.price));

        long maxComfortSum = 0;

        // 处理每个房子
        for (House house : houses) {
            Map.Entry<Long, Integer> entry = friends.ceilingEntry(house.price);
            if (entry != null) {
                // 找到第一个不小于房子价格的金币数量
                maxComfortSum += house.comfort;
                int count = entry.getValue();
                if (count == 1) {
                    // 如果该数量的金币只剩下一个，则移除
                    friends.remove(entry.getKey());
                } else {
                    // 否则减少其计数
                    friends.put(entry.getKey(), count - 1);
                }
            }
        }

        // 输出最大舒适度之和
        System.out.println(maxComfortSum);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

from sortedcontainers import SortedList

class House:
    def __init__(self, comfort, price):
        self.comfort = comfort
        self.price = price

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    m = int(data[1])
    
    # 读取朋友的金币数量
    friends = SortedList()
    index = 2
    for _ in range(n):
        gold = int(data[index])
        friends.add(gold)
        index += 1
    
    # 读取房子的舒适度和价格
    houses = []
    for _ in range(m):
        comfort = int(data[index])
        price = int(data[index + 1])
        houses.append(House(comfort, price))
        index += 2
    
    # 按照价格从高到低排序房子
    houses.sort(key=lambda x: x.price, reverse=True)
    
    max_comfort_sum = 0
    
    # 处理每个房子
    for house in houses:
        # 查找第一个不小于房子价格的金币数量
        idx = friends.bisect_left(house.price)
        if idx < len(friends):