P3163. 用户调度问题

解题思路

本题乍一看会以为和 剑指Offer II 91. 粉刷房子 是同一道题。 两道题里都有类似的题目描述：

• 对于每一个用户（房子）都有 3 种可能的选择
• 每次选择具有同样的限制条件，即不能够和上一次的选择一样
• 题目问的都是选择最优的策略使得成本尽可能小

但实际上，这两个题目的所谓 “最优策略” 的含义是不相同的。

• 在 剑指Offer II 91. 粉刷房子 中，最优策略指的是 使得总花费最小的策略。这是一种 全局最优 的策略。
• 在本题中，所谓的最优策略指的是 每个用户都选择使得当前花费最小的策略。这是一种 局部最优 的策略。

因此，虽然在题目描述上这两道题非常类似，但是 解法和代码却是完全不一样的。

进一步思考的话，这实际上也体现了 动态规划 和 贪心 分别适用于解决的问题类型：

• 动态规划 适用于直接计算 全局最优 的问题
• 贪心算法 适用于直接计算 局部最优 的问题（且此处的局部最优结果可以代替全局最优结果）

对于某一个使用动态规划来计算得到全局最优结果的问题，如果它的局部最优结果恰好也等同于全局最优结果，则这个题目也可以使用贪心来解决。 譬如 【DP/贪心】2024E-贪心的商人 就可以同时分别使用贪心和动态规划来解决，正是因为这道题的局部最优结果等于全局最优结果。

回到这道题目本身，本题的 贪心选择策略 是非常简单的，直接按照题面描述来进行每个人的选择即可。

可以定义一个函数 find() 来进行每一次的选择，代码如下：

对于第一次选择，由于没有特定的上一次选择 pre_choice 的要求，我们可以这样调用函数：

除了第一次选择以外的其他选择，都要以上一次的选择结果来作为本次选择的 pre_choice，对应代码如下：

复杂度分析 设 n 为待调度的用户数。

• 时间复杂度：O(n)。主流程对 n 个用户各调用一次 find 函数，而 find 内部只是从索引 2 到 0 逆序扫描固定的 3 种策略、跳过与上一个用户相同的那种，做常数次比较就能选出当前消耗最少（并列时靠后）的策略，所以单次选择是 O(1)；加上读入 n 行输入，总体与用户数成线性关系。
• 空间复杂度：O(n)，用于储存 n 个用户各自三种策略消耗的二维数组 nums；选择过程本身只用了 pre_choice、cur_choice、ans 等常数个变量。