这次没有难题，难度大概是1个平时的t1和3个t3，但是我居然wa了7次，整不会了真。Profile Here。

Question D Minimum Time to Repair Cars

题意

给定一个长为n的数组ranks，表示n个修理工的能力，一个能力为r的修理工可以在$k^2*r$的时间内修理k辆汽车。所有修理工同时开始修理共p辆汽车，问最短多长时间可以完成？

($n\le 1e5, ranks[i]\le 100, p \le 1e6$)

题解

这个是典型的二分答案题目，只要当我们很难直接求解答案，但是我们的数据范围能够付出logp(p为答案的解空间大小)的时间代价将其转换为多项式时间内检验某个答案是否满足条件的问题(P问题)的时候，我们可以考虑用这种方式检验问题。转换后，我们每次检验二分的答案能否满足即可。

代码如下

typedef long long ll;
class Solution {
public:
    vector<int> rk;
    int goal;
    bool check(ll rt){
        ll tot = 0;
        for(int i = 0; i < rk.size(); i++){
            tot += floor(sqrt(rt * 1.0 / rk[i]));
        }
        return tot >= goal;
    }
    long long repairCars(vector<int>& ranks, int cars) {
        rk = ranks, goal = cars;
        ll l = 1, r = 1e14;
        while(l < r){
            ll mid = (l + r) >> 1;
            if(check(mid)){
                r = mid;
            }
            else{
                l = mid + 1;
            }
        }
        return l;
    }
};

Question C Find Score of an Array After Marking All Elements

题意

给定一个含有n个正整数的数组nums。

从 score = 0 开始, 模拟下列过程:

• 在nums数组中选择一个最小的未被标记的元素nums[i]，如果有相同的元素，选择最小的那个下标。
• score += nums[i]
• 标记选中的元素和其相邻的元素nums[i-1]和nums[i+1]
• 重复上述操作直至所有元素被标记

求上述过程结束之后score的值。
($n \le 1e5, a[i] \le 1e6$)

题解

我们肯定需要一种比较高效的维护方式来找到未被标记的最小元素，且相同元素还能找到最小的那个下标。如果纯暴力的话，即每次通过遍历一次数组的方式找到这个元素，实际上复杂度要$O(n^2)$，肯定是不能接受的。

考虑对每个key维护一个set，这个set即包括所有未被标记的元素大小为key的下标集合。这个map[HTML_REMOVED]> mp的数据结构就维护了所有没有被标记的元素下标，且这个数据结构可以帮助找到最小的未标记元素。每次标记元素的时候，只需要将这个需要标记的元素从mp中移除出去即可。

思路很简单，但是我tle了一次的原因是什么呢set<int>& itv = it->second;这里忘记加引用号了，如果没有引用号就相当于会重新进行一次值拷贝，导致复杂度就爆炸了！正确代码如下：

typedef long long ll;
class Solution {
public:
    long long findScore(vector<int>& nums) {
        ll ret = 0;
        int n = nums.size();
        vector<int> flag(n, 1);
        map<int, set<int>> mp;
        for(int i = 0; i < n; i++){
            mp[nums[i]].insert(i);
        }
        while(mp.size() > 0){
            auto it = mp.begin();
            int itk = it->first;
            set<int>& itv = it->second;
            auto itvf = itv.begin();

            ret += itk;

            int lidx = (*itvf) - 1, idx = (*itvf), ridx = (*itvf) + 1;
            if(lidx >= 0 && lidx < n && flag[lidx]){
                flag[lidx] = 0, mp[nums[lidx]].erase(lidx);
                if(mp[nums[lidx]].size() == 0) mp.erase(nums[lidx]);
            }
            if(ridx >= 0 && ridx < n && flag[ridx]){
                flag[ridx] = 0, mp[nums[ridx]].erase(ridx);
                if(mp[nums[ridx]].size() == 0) mp.erase(nums[ridx]);
            }

            flag[idx] = 0, mp[nums[idx]].erase(idx);
            if(mp[nums[idx]].size() == 0) mp.erase(nums[idx]);
        }
        return ret;
    }
};

Question B Maximize Greatness of an Array

题意

给定一个长为n的数组a[1:n]，可以对这个数组a进行任意重排为一个新的等长数组perm，求最多能有多少个位置满足perm[i]>a[i]？

($n\le 1e5, a[i] \le 1e9$)

题解

贪心，首先对a从小到大排序。

然后从小到大看一下数组a中，有哪个最小且还没有被放入perm中的元素比a[i]大。

class Solution {
public:
    int maximizeGreatness(vector<int>& a) {
        int n = a.size();
        sort(a.begin(), a.end());
        int ret = 0, idy = 0;
        for(int i = 0; i < n && idy < n; i++){
            while(idy < n){
                if(a[idy] <= a[i])
                    idy++;
                else{
                    ret++, idy++;
                    break;
                }
            }
        }
        return ret;
    }
};

Question A Distribute Money to Maximum Children

题意

不想翻译了，直接贴过来了…

You are given an integer money denoting the amount of money (in dollars) that you have and another integer children denoting the number of children that you must distribute the money to.
You have to distribute the money according to the following rules:
All money must be distributed.
Everyone must receive at least 1 dollar.
Nobody receives 4 dollars.
Return the maximum number of children who may receive exactly 8 dollars if you distribute the money according to the aforementioned rules. If there is no way to distribute the money, return -1.

题解

理解题意就可以。不知道为什么要设计这么多规则约束，是为了避免gpt4自动代码生成过题吗，wa了很多次。

class Solution {
public:
    int distMoney(int money, int children) {
        if(money < children || (money == 4 && children == 1)) return -1;
        if(money == children * 8) return children;
        if(money > children * 8) return children - 1;
        money -= children;
        return (money / 7) - (money % 7 == 3 && children - money / 7 == 1 ? 1 : 0);
    }
};