E卷-刷题笔记合集🔗

预订酒店

问题描述

暑假来临，卢小姐计划前往某个旅游景点游玩。他在网上搜索到了各种价位的酒店，这些酒店的价格存储在一个长度为 的数组 中。卢小姐的心理价位是 元。现在，请你帮助卢小姐从这些酒店中筛选出 个价格最接近 元的酒店（），并按照价格从低到高的顺序打印这些酒店的价格。

输入格式

第一行包含三个整数 、 和 ，分别表示酒店数量、需要筛选的酒店数量和卢小姐的心理价位。

第二行包含 个整数 ，表示每家酒店的价格。

输出格式

输出一行，包含 个整数，表示筛选出的 个酒店的价格，按照从低到高的顺序排列。

样例输入1

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

样例输出1

4 5 6 7 8

样例输入2

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

样例输出2

4 5 6 7

样例输入3

6 3 1000
30 30 200 500 70 300

样例输出3

200 300 500

样例解释

数据范围

题解

优先队列

这道题目的核心是找出最接近目标价格的 个酒店。我们可以通过以下步骤来解决这个问题：

1. 首先需要计算每个酒店价格与目标价格 的差值的绝对值。
2. 我们可以根据这个差值对酒店进行排序。
3. 最后，选择差值最小的 个酒店，并按照价格从低到高输出。

关键点在于如何高效地进行排序和选择。可以使用快速选择算法（Quick Select）来找到第 小的差值，这样就可以在 的时间复杂度内完成选择。

对于排序，只需要对选出的 个酒店进行排序，时间复杂度为 。

总的时间复杂度为 ，对于给定的数据范围（，）来说是可以接受的。

参考代码

• Python

import heapq

def find_closest_hotels(n, k, x, prices):
    # 创建一个最大堆，用于存储k个最接近x的酒店价格
    pq = []
    
    for price in prices:
        # 计算当前价格与目标价格的差值
        diff = abs(price - x)
        
        # 如果堆的大小小于k，直接添加
        if len(pq) < k:
            heapq.heappush(pq, (-diff, -price))
        else:
            # 如果当前差值小于堆顶元素，替换堆顶元素
            if diff < -pq[0][0] or (diff == -pq[0][0] and price < -pq[0][1]):
                heapq.heappop(pq)
                heapq.heappush(pq, (-diff, -price))
    
    # 提取结果并排序
    result = sorted([-price for _, price in pq])
    return result

# 读取输入
n, k, x = map(int, input().split())
prices = list(map(int, input().split()))

# 调用函数找到最接近的酒店
closest_hotels = find_closest_hotels(n, k, x, prices)

# 输出结果
print(*closest_hotels)

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

// 定义一个结构体来存储价格和与目标价格的差值
typedef struct {
    int price;
    int diff;
} Hotel;

// 比较函数，用于qsort
int compare(const void* a, const void* b) {
    Hotel* h1 = (Hotel*)a;
    Hotel* h2 = (Hotel*)b;
    if (h1->diff != h2->diff)
        return h1->diff - h2->diff;
    return h1->price - h2->price;
}

// 比较函数，用于最终排序
int compare_price(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int main() {
    int n, k, x;
    scanf("%d %d %d", &n, &k, &x);

    Hotel* hotels = (Hotel*)malloc(n * sizeof(Hotel));

    // 读取价格并计算差值
    for (int i = 0; i < n; i++) {
        scanf("%d", &hotels[i].price);
        hotels[i].diff = abs(hotels[i].price - x);
    }

    // 排序
    qsort(hotels, n, sizeof(Hotel), compare);

    // 选择前k个价格
    int* result = (int*)malloc(k * sizeof(int));
    for (int i = 0; i < k; i++) {
        result[i] = hotels[i].price;
    }

    // 对结果进行排序
    qsort(result, k, sizeof(int), compare_price);

    // 输