第 100 场双周赛

6323. 将钱分给最多的儿童

分情况讨论，坑较多。可用每个儿童预先分 $1$ 美元，保证最后每个儿童都能分到钱，分情况讨论不会特别复杂。

class Solution {
public:
    int distMoney(int money, int children) {
        // 保证每个儿童都能分到 1 美元
        money -= children;
        // 如果钱不够分
        if (money < 0) return -1;
        // 如果只有一个儿童，并且只有 4 美元
        if (money == 3 && children == 1) return -1;
        int res = 0;
        // 贪心分配
        while (money >= 7 && children > 0) {
            children -= 1;
            money -= 7;
            res += 1;
        }
        // 如果儿童都被分到钱，如果还剩下钱需要分给最后一个儿童
        if (children == 0) {
            if (money == 0)
                return res;
            else
                return res - 1;
        }
        // 如果恰好余剩 4 美元给最后一个儿童，则需要分给上一个儿童
        if (money == 3 && children == 1)
            return res - 1;
        else
            return res;
    }
};

6324. 最大化数组的伟大值

排序 + 快慢指针，快指针每次走一步，检查快指针位置的值是否大于慢指针位置的值，如果大于则慢指针加一。

class Solution {
public:
    int maximizeGreatness(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        // i 是快指针，j 是慢指针
        int i = 0, j = 0;
        int res = 0;
        while (i < nums.size()) {
            if (nums[i] > nums[j]) {
                res += 1;
                ++j;
            }
            ++i;
        }
        return res;
    }
};

6351. 标记所有元素后数组的分数

排序 + 模拟，只是不是对值排序，而是排序索引位置。根据排序后的索引位置逐个操作即可。

class Solution {
public:
    long long findScore(vector<int>& nums) {
        // 记录是否被标记
        vector<bool> used(nums.size(), false);
        long long score = 0;
        // 创建索引数组，并以 (val, index) 为标准排序
        vector<int> indexOrder(nums.size());
        for (int i = 0; i < nums.size(); ++i) {
            indexOrder[i] = i;
        }
        sort(indexOrder.begin(), indexOrder.end(), [&nums](int i, int j) {
            if (nums[i] == nums[j]) return i < j;
            return nums[i] < nums[j];
        });
        // 模拟操作
        for (int index : indexOrder) {
            if (used[index]) continue;
            score += nums[index];
            if (index > 0) used[index - 1] = true;
            if (index < nums.size() - 1) used[index + 1] = true;
            used[index] = true;
        }
        return score;
    }
};

6325. 修车的最少时间

常规做法是二分答案，还可能由数学法或堆模拟。下面使用二分答案来做。

首先分析题目：

设求的目标答案为 $R$，第 $i$ 个机械工修车数量为 $m_i$，那么第 $i$ 个工人花费的时间为

$$\mathrm{ranks}[i] \cdot m_i ^2$$

本题的答案为

$$R = \argmin_{m} \max_i \{ \mathrm{ranks}[i] \cdot m_i ^2 \}$$

约束为

$$\mathrm{s.t.} \quad \sum_i m_i = \mathrm{cars}$$

当然这种规划（组合优化）问题一般难以求数学解，一般通过技巧性解法。本题的答案显然是单调的，对于 $R$，$R + k$ 显然满足条件，而 $R - k$ 不满足条件（$k > 0$），所以可用二分答案。

#define ll long long

class Solution {
public:
    long long repairCars(vector<int>& ranks, int cars) {
        int rank_count[101] = {0};
        for (int rank : ranks) rank_count[rank]++;
        ll left = 0, right = 100ll * cars * cars;
        // 二分答案
        while (left < right) {
            ll mid = (left + right) / 2;
            ll repaired = 0;
            // 统计当前答案下所能修的最多汽车数量，如果达到目标则设置为 right
            for (int i = 1; i <= 100; ++i) {
                if (rank_count[i] == 0) continue;
                ll temp = (ll)sqrt(mid / i);
                repaired += temp * rank_count[i];
                // 如果已经可以修完所有的车，就直接结束循环
                if (repaired >= cars) break;
            }
            if (repaired >= cars) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }
};