leetcode 2594. 修车的最少时间

题目描述

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

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

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

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

示例 1：

输入：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 分钟是修理完所有车需要的最少时间。

示例 2：

输入：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⁵
1 <= ranks[i] <= 100
1 <= cars <= 10⁶

题解——堆模拟

思路

第一反应没想到二分，用的是模拟。有一个很显然的思路：贪心地依次安排每一辆车的归属。如果r1*(n1+1)^2>r2*(n2+1)^2，则安排给r2更好。这种贪心策略显然是正确的。
很直接的实现是：为了找到r*n^2最小的那个工人，使用优先队列，重载运算符进行自定义排序。这样的时间复杂度将是O(cars*log(ranks))，大概是2e7的量级，果真超时了。
注意到，ranks[i]的范围仅为[1,100]，而rank和n相同的工人是没有区别的。比如说，第i辆车安排给了rank为a，n为b的工人，假如还有rank为a，n为b的工人，那第i+1辆车一定安排给他。所以我们可以对rank相同的工人进行统一安排。具体方法就是在我们的{r,n}二元组中添加一个{cnt}元素。，记录rank相同的工人个数(由于一开始n都为0，这些工人之后的n也都会相同，除非cars已经不够了)
优化后的最坏时间复杂度成为O(cars*log(100))（在ranks为1~100，cars=1e6时出现），大概是1e7的量级，其实也容易卡掉。不过这题的数据比较弱，没有构造太多这样的用例，相反，本题的大样例将ranks做得很大，反而会减少循环次数，比如说1e5个ranks平均分配，每次循环都会减去1e3，只需要循环1e3次即可。

代码

class PR {//保存r，n和人数
public:
    long long r,n,cnt;
    PR(int a,int b,int c):r(a),n(b),cnt(c){}
    // 重载大于运算符
    bool operator>(const PR &b) const {//
        long long p=this->r,q=this->n,x=b.r,y=b.n;
        return p*(q+1)*(q+1)>x*(y+1)*(y+1);
    }
};
class Solution {
public:
    long long repairCars(vector<int>& ranks, int cars) {
        priority_queue<PR,vector<PR>,greater<>> pq;//小根堆
        long long ans=0;
        vector<int> cnt(101);
        for(int num:ranks)//记录人数
            ++cnt[num];
        for(int i=1;i<=100;++i)//入堆
            if(cnt[i])
                pq.push(PR(i,0,cnt[i]));
        while(cars)
        {
            auto [r,n,c]=pq.top();
            pq.pop();
            ans=max(ans,r*(n+1)*(n+1));
            if(c>=cars)
                return ans;
            else
                cars-=c;
            pq.push(PR(r,n+1,c));
        }
        return ans;
    }
};