T1.因为山就在那里 - 小米机试真题题解

题目描述

作为一个登山爱好者，Bob现在正计划向珠峰发起挑战，要问为什么的话，因为山就在那里！珠峰的气候变幻莫测，并不是每天都适合登山，但Bob通过东方神秘力量了解到接下来有n个特定日期可能会是适合登山的好日子。因此他在这n天一定要在珠峰大本营等待良机。

然而，海拔5200米的珠峰大本营不是久居之地。根据医生的评估，Bob最多能够在此处生活的总天数为k天，否则出现生命危险的概率将大大增加。因此Bob需要注意在不适合登山的日子下撤回低海拔地区。下撤回低海拔地区和前往珠峰大本营的旅费不可小觑，Bob自身也讨厌频繁移动。

因此请你告诉他，在不错过n个特定日期，同时在珠峰大本营生活不超过总共k天的前提下，最少需要多少次移动？注意，Bob一开始位于低海拔地区，最终也必须回到低海拔地区。一次移动指的是单程而非往返，即从低海拔地区前往珠峰大本营或从珠峰大本营下撤回低海拔地区分别是一次移动。

输入描述

第一行两个正整数n，k，表示可能适合登山的日子天数和Bob最多能在珠峰大本营生活的天数 ;

第二行n个正整数ai，表示第i个可能适合登山的日子是接下来的第ai天，保证递增。

输出描述

一行，输出一个正整数，表示最少的移动次数。

示例1

输入：
5 8
2 3 5 6 10

输出：
4

C++

#include <bits/stdc++.h>

using namespace std;

int main() {
    // 适合登山的日子天数n, 和最多能在珠峰大本营生活的天数k
    int n, k;
    cin >> n >> k;
    vector<int> days(n);
    // 读取所有适合登山的日期
    for (int i = 0; i < n; i++) cin >> days[i];

    sort(days.begin(), days.end());

    // 下撤回低海拔地区可以休息的天数
    vector<int> gapDays;
    for (int i = 1; i < n; i++) {
        int gap = days[i] - days[i - 1] - 1; // 空挡天数
        // 只有空挡天数大于0的才有意义
        if (gap > 0) gapDays.push_back(gap);
    }
    // 降序排序
    sort(gapDays.begin(), gapDays.end(), greater<>());

    // 如果不下来一只在大本营生活的天数
    int total = days[n - 1] - days[0] + 1;

    // 在大本营生活的天数超过了最多能在珠峰大本营生活的天数k必须下撤低海拔地区
    int idx = 0;
    // 贪心的先选择空挡时间多的区间进行下撤低海拔地区
    while (total > k && idx < gapDays.size()) {
        total -= gapDays[idx++]; // 减少停留天数
    }

    // idx * 2 次单程移动 + 第一次上去和最后一次下来
    cout << idx * 2 + 2 << endl;
    return 0;
}

题目分析

这个问题涉及的是 贪心算法，目标是在满足以下条件的前提下，最小化Bob的移动次数：

• 适合登山的日期已经确定，并且必须在这些日期中停留；
• Bob最多能够在珠峰大本营停留k天；
• 初始时Bob在低海拔地区，最终也需要返回低海拔地区；
• 我们需要计算最少的移动次数，即从低海拔地区前往珠峰大本营和从大本营下撤的次数。

解题思路

1. 计算总停留天数：
   • 从第一天到最后一天，Bob在大本营的停留天数是：最后一天 - 第一天下来的天数 + 1。
2. 优化停留天数：
   • 如果在大本营的总停留天数超过了Bob的最大可停留天数k，那么就需要尽量减少这个停留天数。
   • 每次选择最大的空挡时间，即在连续两次适合登山的日子之间的空隙，来减少停留天数。
3. 移动次数的计算：
   • 每次Bob从低海拔地区上山或者从大本营下山都算一次移动。上山和下山的总移动次数由空挡的利用程度决定。

具体实现步骤

1. 读取输入并计算出每两个适合登山的日子之间的空挡天数。
2. 排序空挡时间，选择最大的空挡时间来减少Bob在大本营的停留天数。
3. 计算移动次数：
   • 第一次上山和最后一次下山都需要移动，因此这两个是必选的。
   • 每减少一个空挡时间，增加两次移动（上山和下山）。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏