题目描述

给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [a_i, b_i] 表示树中节点 a_i 和 b_i 之间有一条边。再给你一个长度为 n 的数组 coins，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。

一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：

• 收集距离当前节点距离为 2 以内的所有金币，或者
• 移动到树中一个相邻节点。

你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。

如果你多次经过一条边，每一次经过都会给答案加一。

样例

输入：coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：从节点 2 出发，收集节点 0 处的金币，移动到节点 3，收集节点 5 处的金币，然后移动回节点 2。

输入：coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]
输出：2
解释：从节点 0 出发，收集节点 4 和 3 处的金币，移动到节点 2 处，收集节点 7 处的金币，移动回节点 0。

限制

• n == coins.length
• 1 <= n <= 3 * 10^4
• 0 <= coins[i] <= 1
• edges.length == n - 1
• edges[i].length == 2
• 0 <= a_i, b_i < n
• a_i != b_i
• edges 表示一棵合法的树。

算法

(两次递归遍历) $O(n)$

1. 将无根树转为有根树，并令 $0$ 为根节点。
2. 设 $f(u)$ 表示以 $u$ 为根的子树，从 $u$ 出发，收集子树的所有金币经过的最少边数。$f_1(u)$ 表示以 $u$ 为根的子树，距离 $u$ 恰好为 $1$ 的节点中金币的数量。$f_2(u)$ 表示以 $u$ 为根的子树，距离 $u$ 为 $2$ 或以上的节点中金币的数量。
3. 第一次递归遍历，从 $0$ 开始针对每个点求出 $f$、$f_1$ 和 $f_2$。假设当前点为 $u$，对于子节点 $v$，如果 $f_2(v) > 0$，则 $f(u) = f(u) + f(v) + 2$，表示需要走到节点 $v$ 获取 $v$ 及其子树的所有金币后，再返回。$f_1(u) = f_1(u) + coins(v)$。$f_2(u) = f_2(u) + f_1(v) + f_2(v)$。
4. 第二次递归遍历，求解以每个点作为起始点时的最终答案。这里需要引入三个值 $\text{fa_}f$，$\text{fa_}f_1$ 和 $\text{fa_}f_2$，含义是来自于父节点的 $f$、$f_1$ 和 $f_2$，表示起始点从 $u$ 换到 $v$ 过程中，$u$ 原本作为 $v$ 的父节点变到子节点时的值。
5. 第二次递归时，对于当前点 $u$，更新答案，如果 $\text{fa_}f_2 > 0$，则用 $f_u + \text{fa_}f + 2$ 更新答案。否则，用 $f(u)$ 更新答案。这是因为 $fa$ 虽然是名义的父节点，在已经是「子节点」了，需要按照之前的过程把这个子节点的值统计到答案中。
6. 接着枚举 $u$ 的子节点 $v$，转移时，$\text{new_fa_}f_1 = f_1(u) - coins(v) + coins(fa)$，这是因为，距离 $u$ 恰好为 $1$ 的金币个数来自于原来 $f_1(u)$ 中除去 $v$ 的，还有来自于 $u$ 父节点的。同理，计算 $\text{new_fa_}f$ 和 $\text{new_fa_}f_2$ 也是采用同样的思路，但需要考虑 $f_2(v)$ 的情况，具体可以参考代码。

时间复杂度

• 两次递归遍历，每次遍历每个节点仅访问一次，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储图，$f$ 数组和递归的系统栈。

C++ 代码

class Solution {
private:
    vector<vector<int>> graph;
    vector<int> f, f1, f2;
    int ans;

    void solve1(int u, int fa, vector<int> &coins) {
        for (int v : graph[u]) {
            if (v == fa)
                continue;

            solve1(v, u, coins);

            if (f2[v] > 0)
                f[u] += f[v] + 2;

            f1[u] += coins[v];
            f2[u] += f1[v] + f2[v];
        }
    }

    void solve2(int u, int fa, int fa_f, int fa_f1, int fa_f2, vector<int> &coins) {
        if (fa_f2 > 0) ans = min(ans, f[u] + fa_f + 2);
        else ans = min(ans, f[u]);

        for (int v : graph[u]) {
            if (v == fa)
                continue;

            int new_fa_f = fa_f + (fa_f2 > 0 ? 2 : 0) + f[u];
            int new_fa_f1 = f1[u] - coins[v] + (fa != -1 ? coins[fa] : 0);
            int new_fa_f2 = fa_f1 + fa_f2 + f2[u];

            if (f2[v] > 0) {
                new_fa_f -= f[v] + 2;
                new_fa_f2 -= f1[v] + f2[v];
            }

            solve2(v, u, new_fa_f, new_fa_f1, new_fa_f2, coins);
        }
    }

public:
    int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
        const int n = coins.size();

        graph.resize(n);

        for (const auto &e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }

        f.resize(n, 0);
        f1.resize(n, 0);
        f2.resize(n, 0);

        solve1(0, -1, coins);

        ans = INT_MAX;

        solve2(0, -1, 0, 0, 0, coins);

        return ans;
    }
};

题目描述

给你一个正整数数组 nums。

同时给你一个长度为 m 的整数数组 queries。第 i 个查询中，你需要将 nums 中所有元素变成 queries[i]。你可以执行以下操作 任意 次：

• 将数组里一个元素 增大 或者 减小 1。

请你返回一个长度为 m 的数组 answer，其中 answer[i] 是将 nums 中所有元素变成 queries[i] 的 最少 操作次数。

注意，每次查询后，数组变回最开始的值。

样例

输入：nums = [3,1,6,8], queries = [1,5]
输出：[14,10]
解释：第一个查询，我们可以执行以下操作：
- 将 nums[0] 减小 2 次，nums = [1,1,6,8]。
- 将 nums[2] 减小 5 次，nums = [1,1,1,8]。
- 将 nums[3] 减小 7 次，nums = [1,1,1,1]。
第一个查询的总操作次数为 2 + 5 + 7 = 14。
第二个查询，我们可以执行以下操作：
- 将 nums[0] 增大 2 次，nums = [5,1,6,8]。
- 将 nums[1] 增大 4 次，nums = [5,5,6,8]。
- 将 nums[2] 减小 1 次，nums = [5,5,5,8]。
- 将 nums[3] 减小 3 次，nums = [5,5,5,5]。
第二个查询的总操作次数为 2 + 4 + 1 + 3 = 10。

输入：nums = [2,9,6,3], queries = [10]
输出：[20]
解释：我们可以将数组中所有元素都增大到 10，总操作次数为 8 + 1 + 4 + 7 = 20。

限制

• n == nums.length
• m == queries.length
• 1 <= n, m <= 10^5
• 1 <= nums[i], queries[i] <= 10^9

算法

(排序，前缀和，二分) $O((n + m) \log n)$

1. 将数组从小到大排序，并求出前缀和数组。
2. 对于一个询问 $x$，二分找到分界点 $p$，使得排序后的数组在下标 $[0, p - 1]$ 的数字都小于 $x$，$[p, n - 1]$ 的部分都大于等于 $x$。
3. 通过前缀和数组，分别可求出前后两段的总和为 $s_1$ 和 $s_2$，则这个询问的答案就是 $xp - s_1 + s_2 - x(n - p)$。

时间复杂度

• 排序并求前缀和的时间复杂度为 $O(n \log n)$。
• 对于每个询问，计算答案的时间复杂度为 $O(\log n)$。
• 故总时间复杂度为 $O((n + m) \log n)$。

空间复杂度

• 需要 $O(m + \log n)$ 的额外空间存储答案和排序的系统栈。

C++ 代码

#define LL long long

class Solution {
public:
    vector<LL> minOperations(vector<int>& nums, vector<int>& queries) {
        const int n = nums.size();
        const int m = queries.size();

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

        vector<LL> sum(n);

        sum[0] = nums[0];
        for (int i = 1; i < n; i++)
            sum[i] = sum[i - 1] + nums[i];

        vector<LL> ans(m, 0);
        for (int i = 0; i < m; i++) {
            int x = queries[i];
            int p = lower_bound(nums.begin(), nums.end(), x) - nums.begin();

            ans[i] += sum[n - 1] - (p > 0 ? sum[p - 1] : 0) - (LL)(x) * (n - p);
            if (p > 0)
                ans[i] += (LL)(x) * p - sum[p - 1];
        }

        return ans;
    }
};

题目描述

给你一个下标从 0 开始的整数数组 nums，数组长度为 n。

你可以执行无限次下述运算：

• 选择一个之前未选过的下标 i，并选择一个 严格小于 nums[i] 的质数 p，从 nums[i] 中减去 p。

如果你能通过上述运算使得 nums 成为严格递增数组，则返回 true；否则返回 false。

严格递增数组 中的每个元素都严格大于其前面的元素。

样例

输入：nums = [4,9,6,10]
输出：true
解释：
在第一次运算中：选择 i = 0 和 p = 3，然后从 nums[0] 减去 3，nums 变为 [1,9,6,10]。
在第二次运算中：选择 i = 1 和 p = 7，然后从 nums[1] 减去 7，nums 变为 [1,2,6,10]。
第二次运算后，nums 按严格递增顺序排序，因此答案为 true 。

输入：nums = [6,8,11,12]
输出：true
解释：nums 从一开始就按严格递增顺序排序，因此不需要执行任何运算。

输入：nums = [5,8,3]
输出：false
解释：可以证明，执行运算无法使 nums 按严格递增顺序排序，因此答案是 false。

限制

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
• nums.length == n

算法

(贪心) $O(n + m)$

1. 显然，每次运算都尽可能的使前面的数字变小，才有可能满足严格递增。
2. 使用线性筛，预处理范围内的正整数的质数标记。这里可以假设 $0$ 也是质数，因为减去 $0$ 相当于没有操作，也是合法的。
3. 遍历数组，同时定义变量 $x$，表示当前数字完成运算后最终的值，初始时令 $x = 1$。对于当前数字 $nums(i)$，不断增加 $x$，直到 $nums(i) - x$ 是质数。如果在小于等于 $nums(i)$ 的范围内找不到这样的 $x$，则返回 false。
4. 遍历完数组后，返回 true。

时间复杂度

• 假设数字的范围是 $O(m)$，则线性筛的时间复杂度为 $O(m)$。
• 遍历数组判定的时间复杂度为 $O(n + m)$。
• 故总时间复杂度为 $O(n + m)$。

空间复杂度

• 需要 $O(m)$ 的额外空间存储线性筛的数据结构和标记数组。

C++ 代码

const int N = 1010;

class Solution {
private:
    vector<int> p;
    bool mark[N]; // mark(i) 为 false 则是质数

    void init_prime() {
        mark[1] = true;

        for (int i = 2; i < N; i++) {
            if (!mark[i])
                p.push_back(i);

            for (int j = 0; j < p.size() && i * p[j] < N; j++) {
                mark[i * p[j]] = true;

                if (i % p[j] == 0)
                    break;
            }
        }
    }

public:
    bool primeSubOperation(vector<int>& nums) {
        init_prime();

        const int n = nums.size();

        for (int i = 0, x = 1; i < n; i++) {
            while (x <= nums[i] && mark[nums[i] - x])
                x++;

            if (x > nums[i])
                return false;

            x++;
        }

        return true;
    }
};

题目描述

袋子中装有一些物品，每个物品上都标记着数字 1、0 或 -1。

给你四个非负整数 numOnes、numZeros、numNegOnes 和 k。

袋子最初包含：

• numOnes 件标记为 1 的物品。
• numZeroes 件标记为 0 的物品。
• numNegOnes 件标记为 -1的物品。

现计划从这些物品中恰好选出 k 件物品。返回所有可行方案中，物品上所标记数字之和的最大值。

样例

输入：numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2
输出：2
解释：袋子中的物品分别标记为 {1, 1, 1, 0, 0}。
取 2 件标记为 1 的物品，得到的数字之和为 2。
可以证明 2 是所有可行方案中的最大值。

输入：numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4
输出：3
解释：袋子中的物品分别标记为 {1, 1, 1, 0, 0}。
取 3 件标记为 1 的物品，1 件标记为 0 的物品，得到的数字之和为 3。
可以证明 3 是所有可行方案中的最大值。

限制

• 0 <= numOnes, numZeros, numNegOnes <= 50
• 0 <= k <= numOnes + numZeros + numNegOnes

算法

(分类讨论) $O(1)$

1. 如果 $k \le numOnes$，则显然可以取 $k$ 个标记为 1 的物品，返回 $k$。
2. 如果 $numOnes < k \le numOnes + numZeros$，则可以取全部标记为 1 的物品，再取 $k - numOnes$ 个标记为 0 的物品，返回 $numOnes$。
3. 如果 $numOnes + numZeros < k$，则至少需要取 $k - numOnes - numZeros$ 个标记为 -1 的物品，返回 $numOnes - (k - numOnes - numZeros)$。

时间复杂度

• 三次判断，故时间复杂度为常数。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        if (k <= numOnes)
            return k;

        k -= numOnes;
        if (k <= numZeros)
            return numOnes;

        k -= numZeros;

        return numOnes - k;
    }
};

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个整数 value。

在一步操作中，你可以对 nums 中的任一元素加上或减去 value。

• 例如，如果 nums = [1,2,3] 且 value = 2，你可以选择 nums[0] 减去 value，得到 nums = [-1,2,3]。

数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。

• 例如，[-1,2,3] 的 MEX 是 0，而 [1,0,3] 的 MEX 是 2。

返回在执行上述操作 任意次 后，nums 的最大 MEX 。

样例

输入：nums = [1,-10,7,13,6,8], value = 5
输出：4
解释：执行下述操作可以得到这一结果：
- nums[1] 加上 value 两次，nums = [1,0,7,13,6,8]
- nums[2] 减去 value 一次，nums = [1,0,2,13,6,8]
- nums[3] 减去 value 两次，nums = [1,0,2,3,6,8]
nums 的 MEX 是 4。可以证明 4 是可以取到的最大 MEX。

输入：nums = [1,-10,7,13,6,8], value = 7
输出：2
解释：执行下述操作可以得到这一结果：
- nums[2] 减去 value 一次，nums = [1,-10,0,13,6,8]
nums 的 MEX 是 2。可以证明 2 是可以取到的最大 MEX。

限制

• 1 <= nums.length, value <= 10^5
• -10^9 <= nums[i] <= 10^9

算法

(思维题) $O(n + value)$

1. 每个数字最终通过增减能变成的数字，其模 $value$ 的余数都是确定的，所以统计出每个数字模 $value$ 后，每种余数的个数。
2. 找到出现次数最少的余数的个数，假设为 $m$。
3. 接着找到尽可能小的余数，且满足其个数就是最小值 $m$，记为 $x$，则最终答案就是 $m \cdot value + x$。这是因为，有至少 $m$ 个完整的 $[0, value - 1]$ 的余数，则可以组成 $[0, m * value - 1]$ 这些数字。第一次遇到不足 $m + 1$ 的余数 $x$，就可以知道第一个无法得到的非负整数。

时间复杂度

• 遍历所有数字一次，遍历余数数组两次，故时间复杂度为 $O(n + value)$。

空间复杂度

• 需要 $O(value)$ 的额外空间存储每个余数的个数。

C++ 代码

class Solution {
public:
    int findSmallestInteger(vector<int>& nums, int value) {
        vector<int> r(value, 0);

        for (int x : nums)
            ++r[(x % value + value) % value];

        int mi = INT_MAX;
        for (int i = 0; i < value; i++)
            if (mi > r[i])
                mi = r[i];

        for (int i = 0; i < value; i++)
            if (mi == r[i])
                return mi * value + i;

        return -1;
    }
};

题目描述

给你一个由正整数组成的数组 nums 和一个 正 整数 k。

如果 nums 的子集中，任意两个整数的绝对差均不等于 k，则认为该子数组是一个 美丽 子集。

返回数组 nums 中 非空 且 美丽 的子集数目。

nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。

样例

输入：nums = [2,4,6], k = 2
输出：4
解释：数组 nums 中的美丽子集有：[2], [4], [6], [2, 6]。
可以证明数组 [2,4,6] 中只存在 4 个美丽子集。

输入：nums = [1], k = 1
输出：1
解释：数组 nums 中的美丽数组有：[1]。
可以证明数组 [1] 中只存在 1 个美丽子集。 

限制

• 1 <= nums.length <= 20
• 1 <= nums[i], k <= 1000

算法

(递归回溯) $O(m + 2^n)$

1. 递归枚举每个数字选还是不选。定义长度为 $m$ 的数组，用于记录每个数字标记的次数，其中 $m$ 为最大的数字。
2. 如果当前选这个数字 $x$，需要满足这个数字没被标记过，且选了之后，标记 $x - k$ 和 $x + k$。

时间复杂度

• 初始化标记数组的时间复杂度为 $O(m)$。
• 每个数字有两种选择，故递归的时间复杂度为 $O(2^n)$。
• 故总时间复杂度为 $O(m + 2^n)$。

空间复杂度

• 需要 $O(m + n)$ 的额外空间存储标记数组和递归的系统栈。

C++ 代码

const int N = 1010;

class Solution {
private:
    int n, ans;
    int seen[N];

    void solve(int i, const vector<int> &nums, int k) {
        if (i == n) {
            ans++;

            return;
        }

        solve(i + 1, nums, k);

        if (seen[nums[i]] > 0)
            return;

        if (nums[i] + k < N) ++seen[nums[i] + k];
        if (nums[i] - k > 0) ++seen[nums[i] - k];

        solve(i + 1, nums, k);

        if (nums[i] + k < N) --seen[nums[i] + k];
        if (nums[i] - k > 0) --seen[nums[i] - k];
    }

public:
    int beautifulSubsets(vector<int>& nums, int k) {
        memset(seen, 0, sizeof(seen));
        n = nums.size();

        ans = 0;
        solve(0, nums, k);

        return ans - 1;
    }
};

题目描述

骑士在一张 n x n 的棋盘上巡视。在有效的巡视方案中，骑士会从棋盘的 左上角 出发，并且访问棋盘上的每个格子 恰好一次。

给你一个 n x n 的整数矩阵 grid，由范围 [0, n * n - 1] 内的不同整数组成，其中 grid[row][col] 表示单元格 (row, col) 是骑士访问的第 grid[row][col] 个单元格。骑士的行动是从下标 0 开始的。

如果 grid 表示了骑士的有效巡视方案，返回 true；否则返回 false。

注意，骑士行动时可以垂直移动两个格子且水平移动一个格子，或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。

样例

输入：grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]
输出：true
解释：grid 如上图所示，可以证明这是一个有效的巡视方案。

输入：grid = [[0,3,6],[5,8,1],[2,7,4]]
输出：false
解释：grid 如上图所示，考虑到骑士第 7 次行动后的位置，第 8 次行动是无效的。

限制

• n == grid.length == grid[i].length
• 3 <= n <= 7
• 0 <= grid[row][col] < n * n
• grid 中的所有整数 互不相同。

算法1

(预处理) $O(n^2)$

1. 预处理 $grid$ 每个整数的下标对，然后按顺序遍历，判断相邻的下标对是否合法。

时间复杂度

• 遍历数组一次，按顺序遍历下边一次，故时间复杂度为 $O(n^2)$。

空间复杂度

• 需要 $O(n^2)$ 的额外空间存储下标对。

C++ 代码

class Solution {
public:
    bool checkValidGrid(vector<vector<int>>& grid) {
        const int n = grid.size();

        vector<int> vx(n * n), vy(n * n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                vx[grid[i][j]] = i;
                vy[grid[i][j]] = j;
            }

        if (!(vx[0] == 0 && vy[0] == 0))
            return false;

        for (int i = 1; i < n * n; i++)
            if (!((abs(vx[i] - vx[i - 1]) == 1 && abs(vy[i] - vy[i - 1]) == 2) || 
            (abs(vx[i] - vx[i - 1]) == 2 && abs(vy[i] - vy[i - 1]) == 1)))
                return false;

        return true;
    }
};

算法2

(模拟验证) $O(n^2)$

1. 从 $(0, 0)$ 开始，每次寻找下一个合法的位置，判定其位置上的数字是否合法。

时间复杂度

• 最多遍历遍历数组一次，每次遍历最多访问 $8$ 个方向，故时间复杂度为 $O(n^2)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool checkValidGrid(vector<vector<int>>& grid) {
        const int n = grid.size();
        const int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1};
        const int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};

        if (grid[0][0] != 0)
            return false;

        int x = 0, y = 0;
        for (int i = 1; i < n * n; i++) {
            bool ok = false;

            for (int d = 0; d < 8; d++) {
                int tx = x + dx[d], ty = y + dy[d];
                if (tx < 0 || tx >= n || ty < 0 || ty >= n)
                    continue;

                if (grid[tx][ty] == i) {
                    ok = true;
                    x = tx; y = ty;

                    break;
                }
            }

            if (!ok)
                return false;
        }

        return true;
    }
};

题目描述

给你一个 正 整数 n。

用 even 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的偶数下标的个数。

用 odd 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的奇数下标的个数。

返回整数数组 answer，其中 answer = [even, odd]。

样例

输入：n = 17
输出：[2,0]
解释：17 的二进制形式是 10001。 
下标 0 和 下标 4 对应的值为 1。 
共有 2 个偶数下标，0 个奇数下标。

输入：n = 2
输出：[0,1]
解释：2 的二进制形式是 10。 
下标 1 对应的值为 1。 
共有 0 个偶数下标，1 个奇数下标。

限制

• 1 <= n <= 1000

算法

(模拟) $O(\log n)$

1. 根据题意逐一判断 $n$ 的二进制位。

时间复杂度

• 遍历 $O(\log n)$ 次二进制位，故时间复杂度为 $O(\log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    vector<int> evenOddBit(int n) {
        vector<int> ans(2, 0);

        int b = 0;
        while (n) {
            if (n & 1)
                ++ans[b];

            b ^= 1;
            n >>= 1;
        }

        return ans;
    }
};

题目描述

给你一个整数数组 ranks，表示一些机械工的 能力值。ranks_i 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n^2 分钟内修好 n 辆车。

同时给你一个整数 cars，表示总共需要修理的汽车数目。

请你返回修理所有汽车 最少 需要多少时间。

注意：所有机械工可以同时修理汽车。

样例

输入：ranks = [4,2,3,1], cars = 10
输出：16
解释：
- 第一位机械工修 2 辆车，需要 4 * 2 * 2 = 16 分钟。
- 第二位机械工修 2 辆车，需要 2 * 2 * 2 = 8 分钟。
- 第三位机械工修 2 辆车，需要 3 * 2 * 2 = 12 分钟。
- 第四位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
16 分钟是修理完所有车需要的最少时间。

输入：ranks = [5,1,8], cars = 6
输出：16
解释：
- 第一位机械工修 1 辆车，需要 5 * 1 * 1 = 5 分钟。
- 第二位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
- 第三位机械工修 1 辆车，需要 8 * 1 * 1 = 8 分钟。
16 分钟时修理完所有车需要的最少时间。

限制

• 1 <= ranks.length <= 10^5
• 1 <= ranks[i] <= 100
• 1 <= cars <= 10^6

算法

(二分答案) $O(n \log s)$

1. 二分修理的时间，求出每位机械工能修理车辆的数目。
2. 如果总和达到了需要修理的数目，则继续二分下半部分，否则二分上半部分。

时间复杂度

• 二分的区间为 $s = cars \cdot ranks_i$。
• 每次二分的判定时间复杂度为 $O(n)$。
• 故总时间复杂度为 $O(n \log s)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

#define LL long long

class Solution {
private:
    bool check(LL m, const vector<int> &ranks, int cars) {
        LL tot = 0;
        for (int r : ranks) {
            tot += sqrt(m / r);
            if (tot >= cars)
                return true;
        }

        return tot >= cars;
    }

public:
    LL repairCars(vector<int>& ranks, int cars) {
        LL l = 0, r = 100000000000000ll;

        while (l < r) {
            LL mid = (l + r) >> 1;
            if (check(mid, ranks, cars)) r = mid;
            else l = mid + 1;
        }

        return l;
    }
};

题目描述

给你一个数组 nums，它包含若干正整数。

一开始分数 score = 0，请你按照下面算法求出最后分数：

• 从数组中选择最小且没有被标记的整数。如果有相等元素，选择下标最小的一个。
• 将选中的整数加到 score 中。
• 标记 被选中元素，如果有相邻元素，则同时标记 与它相邻的两个元素。
• 重复此过程直到数组中所有元素都被标记。

请你返回执行上述算法后最后的分数。

样例

输入：nums = [2,1,3,4,5,2]
输出：7
解释：我们按照如下步骤标记元素：
- 1 是最小未标记元素，所以标记它和相邻两个元素：[(2,1,3),4,5,2]。
- 2 是最小未标记元素，所以标记它和左边相邻元素：[(2,1,3),4,(5,2)]。
- 4 是仅剩唯一未标记的元素，所以我们标记它：[(2,1,3,4,5,2)]。
总得分为 1 + 2 + 4 = 7。

输入：nums = [2,3,5,1,3,2]
输出：5
解释：我们按照如下步骤标记元素：
- 1 是最小未标记元素，所以标记它和相邻两个元素：[2,3,(5,1,3),2]。
- 2 是最小未标记元素，由于有两个 2，我们选择最左边的一个 2，
    也就是下标为 0 处的 2，以及它右边相邻的元素：[(2,3,5,1,3),2]。
- 2 是仅剩唯一未标记的元素，所以我们标记它：[(2,3,5,1,3,2)]。
总得分为 1 + 2 + 2 = 5。

限制

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6

算法

(堆) $O(n \log n)$

1. 建立一个小跟堆，并维护一个标记数组。
2. 每次从堆中取出最小值，如果这个位置已经被标记，则忽略。
3. 如果没有被标记，则累加答案，并标记相邻位置。
4. 直到堆为空。

时间复杂度

• 建堆后，每个位置出堆一次，故时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储堆和标记数组。

C++ 代码

#define LL long long
#define PII pair<int, int>

class Solution {
public:
    LL findScore(vector<int>& nums) {
        priority_queue<PII, vector<PII>, greater<PII>> heap;
        const int n = nums.size();

        for (int i = 0; i < n; i++)
            heap.push(make_pair(nums[i], i));

        vector<bool> mark(n, false);

        LL ans = 0;
        while (!heap.empty()) {
            PII top = heap.top();
            heap.pop();

            if (mark[top.second])
                continue;

            ans += top.first;

            if (top.second > 0)
                mark[top.second - 1] = true;

            if (top.second < n - 1)
                mark[top.second + 1] = true;
        }

        return ans;
    }
};