科大讯飞笔试 科大讯飞笔试题 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多种语言版本,持续更新中。