E. New Year Parties - 题解

比赛与标签

比赛: Codeforces Round 611 (Div. 3) 标签: dp, greedy 难度: *1800

题目大意喵~

新年派对时间到啦！有 n 个朋友，第 i 个朋友住在数轴上坐标为 x_i 的房子里。为了庆祝新年，每个朋友都可以选择移动到 x_i-1，x_i (待在原地)，或者 x_i+1 的房子里。每个朋友最多只能移动一次哦。

所有朋友都做出了自己的选择之后，我们需要计算他们最终占用了多少个不同的房子。现在的问题是，通过巧妙地安排所有朋友的移动，最终占用的房子数量最少可以是多少，最多又可以是多少呢？

简单来说，就是给你 n 个朋友的初始位置，你要分别计算出最小和最大的“派对场地”数量，的说！

解题思路喵！

这道题要求我们分别计算最小值和最大值，这是一个很强的信号，告诉我们可以把问题拆成两个独立的部分来解决，喵~ 无论是求最小值还是最大值，一个非常关键的预处理步骤就是——排序！

为什喵要排序呢？因为朋友们的移动选择只会影响到坐标邻近的朋友。将初始坐标 x 从小到大排序后，我们就可以从左到右依次处理每个朋友，做出当前最优的决策，而不用担心这个决策会对前面已经处理过的朋友产生影响。这正是贪心算法最喜欢的环境呐！

---

求最小值：大家挤一挤，更热闹喵！

为了让占用的房子数量最少，我们的目标是尽可能让更多的朋友待在同一个房子里。

想象一下，我们按排好序的朋友们一个个来安排住处。对于第 i 个朋友（坐标为 x_i），我们怎么决策才能为后面的朋友创造更多“蹭房”的机会呢？

答案是：当我们不得不为当前这位朋友占用一个新房子时，我们应该让他住到 x_i + 1 去。

为什喵呢？因为 x_i + 1 这个位置是最“靠前”的，它不仅解决了当前朋友 i 的住宿问题，还可能顺便解决了朋友 i+1（坐标 x_{i+1}）和朋友 i+2（坐标 x_{i+2}）的问题！如果 x_{i+1} 恰好是 x_i+1 或者 x_i+2，那他们就可以直接移动到 x_i+1 这个已经点亮的房子里，不用再开新房啦！

所以，我们的贪心策略是：

1. 对所有朋友的坐标 x 进行排序。
2. 从左到右遍历每个朋友 i。
3. 我们用一个变量 last_occupied_pos 记录上一个被占用的房子的位置。
4. 对于当前朋友 i，如果他可以移动到的任何位置（x_i-1, x_i, x_i+1）都已经被之前的朋友覆盖了，那他就不需要占用新房子。具体来说，如果 x_i - 1 <= last_occupied_pos，说明他的活动范围和上一个被占用的房子有交集，他总能找到地方住下。
5. 反之，如果 x_i - 1 > last_occupied_pos，说明他离上一个热闹的派对太远了，必须自己开一个新的派对！这时，我们就让他占用 x_i + 1 这个房子，然后更新 last_occupied_pos = x_i + 1，并且将最少房子数加一。

举个例子：x = [1, 2, 4, 4]

• 朋友1 (at 1): 必须开新房。让他去 1+1=2。min_ans=1, last_occupied=2。
• 朋友2 (at 2): 他可以去 2-1=1, 2, 2+1=3。因为 last_occupied=2，他可以待在 2 号房，这个房子已经被朋友1占了。所以不用开新房。
• 朋友3 (at 4): 他可以去 3, 4, 5。last_occupied=2，4-1=3 > 2，他离得太远了，必须开新房。让他去 4+1=5。min_ans=2, last_occupied=5。
• 朋友4 (at 4): 他可以去 3, 4, 5。last_occupied=5，他可以去 5 号房。不用开新房。 最后，最少需要 2 个房子。

---

求最大值：保持社交距离，喵~

为了让占用的房子数量最多，我们的策略正好相反：尽可能让每个朋友都住进一个全新的、没人住过的房子里。

同样，我们从左到右遍历排好序的朋友们。对于第 i 个朋友，为了给后面的朋友留下更多选择空间，他自己应该尽可能选择一个“靠左”的、还没被占用的新房子。

所以，我们的贪心策略是：

1. 对所有朋友的坐标 x 进行排序。
2. 我们用 last_occupied_pos 记录上一个被占用的房子的位置。
3. 对于当前朋友 i（坐标 x_i），我们按顺序检查 x_i-1, x_i, x_i+1 这三个位置：
   • 首先看 x_i-1：如果 x_i-1 比 last_occupied_pos 大，说明这是个全新的空房！太棒了，就住这！max_ans++，更新 last_occupied_pos = x_i-1。
   • 如果 x_i-1 不行，再看 x_i：如果 x_i 比 last_occupied_pos 大，那就住这儿吧！max_ans++，更新 last_occupied_pos = x_i。
   • 如果 x_i 也不行，最后看 x_i+1：如果 x_i+1 比 last_occupied_pos 大，那就只能住这儿了。max_ans++，更新 last_occupied_pos = x_i+1。
4. 如果三个位置都已经被占了（都小于等于 last_occupied_pos），那这位朋友只好委屈一下，和别人挤一挤了，max_ans 不增加。

这种“从左到右，见缝插针”的策略，保证了我们每一步都尽可能地利用新的空间，从而得到最大的占用数。

代码实现，喵！

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 读取朋友数量 n，喵~
    int n;
    cin >> n;
    
    // 读取每个朋友的初始位置
    vector<int> x(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    
    // 贪心算法的第一步，也是最重要的一步：排序！
    // 就像整理毛线球一样，先把它们排整齐才好下手嘛~
    sort(x.begin(), x.end());
    
    // --- 计算最小值 ---
    // last_min 记录上一个被占用的房子的位置，初始化为一个很小的值
    int last_min = -2;
    int min_ans = 0;
    for (int i = 0; i < n; i++) {
        // 如果当前朋友 x[i] 离上一个占用的房子太远 (x[i]-1 > last_min)
        // 意味着他无论如何都碰不到上一个房子，必须开新房
        if (last_min < x[i] - 1) {
            min_ans++; // 占用了一个新房子
            // 贪心选择：让他住到 x[i]+1，这样可以最大化覆盖范围，
            // 为后面的朋友创造蹭房的机会
            last_min = x[i] + 1;
        }
    }
    
    // --- 计算最大值 ---
    // last_max 记录上一个被占用的房子的位置
    int last_max = -2;
    int max_ans = 0;
    for (int i = 0; i < n; i++) {
        // 尝试为当前朋友找到一个可以住的、最靠左的新房子
        // 他的可选项是 [x[i]-1, x[i]+1]
        // 新房子的位置必须 > last_max
        // 所以他能住的最左新房是 max(last_max + 1, x[i] - 1)
        int candidate = max(last_max + 1, x[i] - 1);
        
        // 检查这个最左的新房子 candidate 是否在他的能力范围 [x[i]-1, x[i]+1] 之内
        if (candidate <= x[i] + 1) {
            max_ans++; // 成功占领新房！
            last_max = candidate; // 更新最后一个被占用的位置
        }
    }
    
    // 输出结果，任务完成啦！
    cout << min_ans << " " << max_ans << endl;
    
    return 0;
}

复杂度分析的说

• 时间复杂度: O(N log N) 的说。 整个算法的瓶颈在于最开始的排序步骤，它的时间复杂度是 O(N log N)。之后计算最小值和最大值的两个循环都只遍历了一次数组，各自是 O(N) 的。所以总的时间复杂度就是 O(N log N + N + N) = O(N log N) 啦。
• 空间复杂度: O(N) 的说。 我们用了一个 vector<int> x 来存储所有朋友的坐标，占用了 O(N) 的空间。如果把输入数组的空间也算上的话就是 O(N)，如果不算的话，额外空间是 O(1) 的，非常优秀！

知识点与总结喵

这道题是贪心思想的绝佳体现，喵~

1. 排序是贪心的好朋友：很多贪心问题，特别是涉及到区间或者数轴上的点时，排序往往是打开局面的金钥匙！
2. 问题分解：将一个复杂问题（同时求最小和最大）分解成两个独立的、更简单的子问题，是重要的解题技巧。
3. 贪心策略的差异：
   • 求最小值的贪心是“向前看”的，做出一个选择（占用 x_i+1）是为了给未来（后面的朋友）创造最大的利益（共享房子）。
   • 求最大值的贪心是“顾眼前”的，为当前朋友选择一个最不影响未来的选项（最左边的空位），从而保全了未来的可能性。 理解这两种不同角度的贪心，对解决类似问题非常有帮助！

希望这次的题解能帮到你哦！多做一些贪心题，就能培养出这种敏锐的直觉啦，加油喵~ 下次再见！