wordpress怎样建立多站点,如何给一个企业的网站做推广,个人网站怎么自己备案,盐城网盐城网站建设站建设华为OD机试真题中的“预定酒店”题目是一道典型的算法题#xff0c;主要考察的是如何在给定的酒店价格数组中找到最接近心理价位的k个酒店#xff0c;并按价格从低到高输出。以下是对该题目的详细解析#xff1a;
一、题目描述
放暑假了#xff0c;小明决定到某旅游景点游…
华为OD机试真题中的“预定酒店”题目是一道典型的算法题主要考察的是如何在给定的酒店价格数组中找到最接近心理价位的k个酒店并按价格从低到高输出。以下是对该题目的详细解析
一、题目描述
放暑假了小明决定到某旅游景点游玩他在网上搜索到了各种价位的酒店长度为n的数组A他的心理价位是x元请帮他筛选出k个最接近x元的酒店nk0并由低到高打印酒店的价格。 备注
1酒店价格数组A和小明的心理价位x均为整型数据(0 nkx 10000)
2优先选择价格最接近心理价位的酒店若两家酒店和心理价位差价相同则选择价格较低的酒店。比如100元和300元距离心理价位200元同样接近此时选择100元;
3酒店价格可能相同重复。
二、输入描述
第一行nkx分别表示酒店价格数组的长度、需要筛选出的酒店数量以及小明的心理价位。第二行A[0] A[1] A[2]…A[n-1]表示酒店的价格数组。
三、输出描述
从低到高打印筛选出的酒店价格。 补充说明 1酒店价格数组A和小明的心理价位x均为整型数据
2优先选择价格最接近心理价位的酒店若两家酒店距离心理价位差价相同则选择价格较低的酒店。比如100元和300元距离心理价位200元同样接近此时选择100元
3酒店价格可能相同重复。
四、示例
示例1
输入5 3 10 12 15 10 9 11输出9 10 11
示例2
输入10 4 6 1 2 3 4 5 6 7 8 9 10输出4 5 6 7
五、解题思路 读取输入 使用Scanner类读取输入的n、k、x以及酒店价格数组A。 计算差值 遍历酒店价格数组A计算每个酒店价格与心理价位x的差值diff |price - x|。创建一个类如HotelPriceDiff或数据结构如Pair来存储价格和差值信息以便后续排序。 排序 使用优先队列最小堆或自定义排序算法对价格和差值信息进行排序。排序规则首先按照差值升序排序如果差值相同则按照价格升序排序。 筛选结果 从排序后的结果中取出前k个酒店价格。由于题目要求按价格从低到高输出可以使用TreeSet或PriorityQueue最小堆来自动排序结果或者手动对结果进行排序。 输出 打印筛选出的k个酒店价格。
六、解题策略 数据结构选择 使用优先队列最小堆可以高效地获取最接近心理价位的k个酒店因为优先队列可以在O(log k)时间内完成插入和删除操作。使用TreeSet可以自动对结果进行排序但需要注意TreeSet的插入和删除操作时间复杂度为O(log n)。 算法效率 遍历酒店价格数组计算差值的时间复杂度为O(n)。优先队列的插入和删除操作时间复杂度为O(log k)因此整体排序的时间复杂度为O(n log k)。如果使用TreeSet进行排序则整体排序的时间复杂度为O(n log n)但在k较小且n较大时优先队列通常更高效。 内存使用 优先队列和TreeSet都会占用额外的内存来存储元素和进行比较操作。如果内存使用是一个关键因素可以考虑使用数组和手动排序算法来减少内存占用。
七、代码实现队列 import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeSet;public class HotelSelection {// 定义一个内部类来存储价格和差值信息static class HotelPriceDiff {int price;int diff;HotelPriceDiff(int price, int diff) {this.price price;this.diff diff;}}public static void main(String[] args) {// 创建Scanner对象以读取输入Scanner scanner new Scanner(System.in);// 读取输入int n scanner.nextInt(); // 酒店数量int k scanner.nextInt(); // 需要选择的酒店数量int x scanner.nextInt(); // 顾客的心理价位// 创建一个数组来存储每家酒店的价格int[] prices new int[n];for (int i 0; i n; i) {prices[i] scanner.nextInt();}// 使用优先队列最小堆来存储价格和差值信息PriorityQueueHotelPriceDiff pq new PriorityQueue((a, b) - {// 自定义比较规则首先按照差值升序排序差值相同则按照价格升序排序if (a.diff ! b.diff) {return Integer.compare(a.diff, b.diff);} else {return Integer.compare(a.price, b.price);}});// 计算每个酒店价格与顾客心理价位的差值并将酒店信息加入优先队列for (int price : prices) {int diff Math.abs(price - x);pq.offer(new HotelPriceDiff(price, diff));}// 从优先队列中取出前k个最接近心理价位的酒店价格TreeSetInteger result new TreeSet(); // 使用TreeSet自动排序结果while (!pq.isEmpty() result.size() k) {result.add(pq.poll().price);}// 打印结果for (int price : result) {System.out.print(price );}}
}八、代码实现数组
import java.util.*; public class HotelReservation { // 定义一个内部类来存储价格和差值 static class PriceDiff { int diff; int price; PriceDiff(int diff, int price) { this.diff diff; this.price price; } } public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 读取输入 int n scanner.nextInt(); int k scanner.nextInt(); int x scanner.nextInt(); int[] prices new int[n]; for (int i 0; i n; i) { prices[i] scanner.nextInt(); } // 计算差值并存储在一个列表中 ListPriceDiff priceDiffs new ArrayList(); for (int price : prices) { int diff Math.abs(price - x); priceDiffs.add(new PriceDiff(diff, price)); } // 根据差值排序如果差值相同则按价格排序 Collections.sort(priceDiffs, Comparator.comparingInt(a - a.diff).thenComparingInt(a - a.price)); // 筛选前k个价格 ListInteger topKPrices new ArrayList(); for (int i 0; i k; i) { topKPrices.add(priceDiffs.get(i).price); } // 对结果排序虽然已经在上一步中按差值排序过但题目要求按价格排序这里再次确保 Collections.sort(topKPrices); // 输出结果 for (int price : topKPrices) { System.out.print(price ); } }
}示例1输入5 3 10 12 15 10 9 11
输出9 10 11九、注意事项
输入验证在实际应用中需要对输入进行验证确保n、k、x以及价格数组A的输入格式正确。性能优化在处理大规模数据时需要注意算法的性能优化如使用更高效的数据结构或算法来减少时间复杂度。边界情况需要考虑边界情况如k等于n、价格数组A中有重复价格等。
十、运行实例解析
输入
10 5 6
1 2 3 4 5 6 7 8 9 10读取输入 n 10表示酒店价格数组的长度。k 5表示需要筛选出的最接近心理价位的酒店数量。x 6表示小明的心理价位。A [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]表示酒店的价格数组。 计算差值 对于每个价格计算其与心理价位x的差值diff |price - x|。 使用优先队列最小堆 创建一个优先队列按照差值升序排序差值相同时按价格升序排序。将每个价格及其差值加入优先队列。 筛选前k个价格 从优先队列中依次取出前k个元素即最接近心理价位的酒店价格。由于优先队列已经按照差值和价格排序所以取出的前k个元素就是符合条件的酒店价格。 输出结果 将筛选出的酒店价格按升序打印出来。
十一、运行步骤 初始化优先队列。 遍历价格数组[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]计算差值并加入优先队列 1差值52差值43差值34差值25差值16差值0最接近7差值18差值29差值310差值4 优先队列中的元素按差值和价格排序将是 (6, 0)(5, 1)(7, 1)(4, 2)(8, 2)(3, 3)(9, 3)(2, 4)(10, 4)(1, 5)但实际上我们只需要前5个 从优先队列中取出前5个元素 65748 打印输出结果 4 5 6 7 8十二、结论
对于给定的输入程序将正确地筛选出最接近心理价位6的5个酒店价格并按升序打印出来。输出结果为4 5 6 7 8与预期相符。
