华为OD机试真题---预定酒店

---

华为OD机试真题中的“预定酒店”题目是一道典型的算法题，主要考察的是如何在给定的酒店价格数组中找到最接近心理价位的k个酒店，并按价格从低到高输出。以下是对该题目的详细解析：

一、题目描述

放暑假了，小明决定到某旅游景点游玩，他在网上搜索到了各种价位的酒店（长度为n的数组A），他的心理价位是x元，请帮他筛选出k个最接近x元的酒店（n>=k>0），并由低到高打印酒店的价格。
备注：

1）酒店价格数组A和小明的心理价位x均为整型数据；(0 < n，k，x < 10000)

2）优先选择价格最接近心理价位的酒店；若两家酒店和心理价位差价相同，则选择价格较低的酒店。（比如100元和300元距离心理价位200元同样接近，此时选择100元）;

3）酒店价格可能相同重复。

二、输入描述

• 第一行：n，k，x，分别表示酒店价格数组的长度、需要筛选出的酒店数量以及小明的心理价位。
• 第二行：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

五、解题思路

1. 读取输入：

   • 使用Scanner类读取输入的n、k、x以及酒店价格数组A。

2. 计算差值：

   • 遍历酒店价格数组A，计算每个酒店价格与心理价位x的差值diff = |price - x|。
   • 创建一个类（如HotelPriceDiff）或数据结构（如Pair）来存储价格和差值信息，以便后续排序。

3. 排序：

   • 使用优先队列（最小堆）或自定义排序算法对价格和差值信息进行排序。
   • 排序规则：首先按照差值升序排序，如果差值相同则按照价格升序排序。

4. 筛选结果：

   • 从排序后的结果中取出前k个酒店价格。
   • 由于题目要求按价格从低到高输出，可以使用TreeSet或PriorityQueue（最小堆）来自动排序结果，或者手动对结果进行排序。

5. 输出：

   • 打印筛选出的k个酒店价格。

六、解题策略

1. 数据结构选择：

   • 使用优先队列（最小堆）可以高效地获取最接近心理价位的k个酒店，因为优先队列可以在O(log k)时间内完成插入和删除操作。
   • 使用TreeSet可以自动对结果进行排序，但需要注意TreeSet的插入和删除操作时间复杂度为O(log n)。

2. 算法效率：

   • 遍历酒店价格数组计算差值的时间复杂度为O(n)。
   • 优先队列的插入和删除操作时间复杂度为O(log k)，因此整体排序的时间复杂度为O(n log k)。
   • 如果使用TreeSet进行排序，则整体排序的时间复杂度为O(n log n)，但在k较小且n较大时，优先队列通常更高效。

3. 内存使用：

   • 优先队列和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();}// 使用优先队列（最小堆）来存储价格和差值信息PriorityQueue<HotelPriceDiff> 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个最接近心理价位的酒店价格TreeSet<Integer> 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();  }  // 计算差值并存储在一个列表中  List<PriceDiff> 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个价格  List<Integer> 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

九、注意事项

1. 输入验证：在实际应用中，需要对输入进行验证，确保n、k、x以及价格数组A的输入格式正确。
2. 性能优化：在处理大规模数据时，需要注意算法的性能优化，如使用更高效的数据结构或算法来减少时间复杂度。
3. 边界情况：需要考虑边界情况，如k等于n、价格数组A中有重复价格等。

十、运行实例解析

输入

10 5 6
1 2 3 4 5 6 7 8 9 10

1. 读取输入：

   • n = 10：表示酒店价格数组的长度。
   • k = 5：表示需要筛选出的最接近心理价位的酒店数量。
   • x = 6：表示小明的心理价位。
   • A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]：表示酒店的价格数组。

2. 计算差值：

   • 对于每个价格，计算其与心理价位x的差值diff = |price - x|。

3. 使用优先队列（最小堆）：

   • 创建一个优先队列，按照差值升序排序，差值相同时按价格升序排序。
   • 将每个价格及其差值加入优先队列。

4. 筛选前k个价格：

   • 从优先队列中依次取出前k个元素（即最接近心理价位的酒店价格）。
   • 由于优先队列已经按照差值和价格排序，所以取出的前k个元素就是符合条件的酒店价格。

5. 输出结果：

   • 将筛选出的酒店价格按升序打印出来。

十一、运行步骤

1. 初始化优先队列。

2. 遍历价格数组[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，计算差值并加入优先队列：

   • 1：差值5
   • 2：差值4
   • 3：差值3
   • 4：差值2
   • 5：差值1
   • 6：差值0（最接近）
   • 7：差值1
   • 8：差值2
   • 9：差值3
   • 10：差值4

   优先队列中的元素（按差值和价格排序）将是：

   • (6, 0)
   • (5, 1)
   • (7, 1)
   • (4, 2)
   • (8, 2)
   • (3, 3)
   • (9, 3)
   • (2, 4)
   • (10, 4)
   • (1, 5)（但实际上我们只需要前5个）

3. 从优先队列中取出前5个元素：

   • 6
   • 5
   • 7
   • 4
   • 8

4. 打印输出结果：

   4 5 6 7 8
   

十二、结论

对于给定的输入，程序将正确地筛选出最接近心理价位6的5个酒店价格，并按升序打印出来。输出结果为4 5 6 7 8，与预期相符。