科大讯飞笔试 科大讯飞笔试题 0727

笔试时间: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):
         

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

2024 BAT笔试合集 文章被收录于专栏

持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解,包含python、C++、Java多种语言版本,持续更新中。

全部评论

相关推荐

2 9 评论
分享
牛客网
牛客企业服务