leetcode 第232场周赛

第三题：leetcode 1792. 最大平均通过率

思路：按 detal定义排序规则，一个一个加

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
            int pass1 = a.first, total1 = a.second, pass2 = b.first, total2 = b.second;
            return 1ll*(total1-pass1)*total2*(total2+1) < 1ll*(total2-pass2)*total1*(total1+1);
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)>q(cmp);
        for(auto x : classes) {
            q.push(make_pair(x[0], x[1]));
        }
        for(int i = 0;i < extraStudents;i++) {
            auto tmp = q.top();q.pop();
            tmp.first++;
            tmp.second++;
            q.push(tmp);
        }
        double ans = 0;
        while(!q.empty()) {
            auto tmp = q.top();q.pop();
            ans += tmp.first*1.0 / tmp.second;
        }
        return ans/classes.size();
    }
};

存在优先队列priority_queue的自定义排序模板：

默认是从大到小排序，定义返回值a<b是从大到小的，与排序不一样

从小到大：

priority_queue<int, vector<int>, greater<int>>q;

自定义排序（重载版）：

struct cmp{
    bool operator() (pair<int, int> &a, pair<int, int> &b){
        int a0 = a.first, a1 = a.second, b0 = b.first, b1 = b.second;
        return (a0+1)*1.0/(a1+1) - a0*1.0/a1 < (b0+1)*1.0/(b1+1) - b0*1.0/b1;
    }
}

priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;

自定义排序（闭包）：

auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
    int pass1 = a.first, total1 = a.second, pass2 = b.first, total2 = b.second;
    return 1ll*(total1-pass1)*total2*(total2+1) < 1ll*(total2-pass2)*total1*(total1+1);
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)>q(cmp);

第四题：1793. 好子数组的最大分数

思路：就是区间最小值*长度，但是区间要经过指定元素

双指针往左右延伸，不能延伸时，取最大值，再继续延伸。

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int l=k, r=k, cur=nums[k], n=nums.size();  // cur为当前区间内的最小值
        int ans = -1;
        while(l >= 0 || r < n) {
            bool flag = false;
            while(l >= 0 && nums[l] >= cur) l--, flag=true;
            while(r < n && nums[r] >= cur)  r++, flag=true;
            ans = max(ans, (r-l-1)*cur);
            // cout << l << " " << r << " " << ans << endl;
            if(l >= 0) {
                if(r < n)  cur = max(nums[l], nums[r]);
                else  cur = nums[l];
            }  else {
                if(r < n) cur = nums[r];
            }
            if(!flag)  break;
        }
        return ans;
    }
};

另一个方法：枚举最小高度，往两边遍历，找到边界，更新答案。

$nlogn$的复杂度，1e5被超时了。。

class Solution {
public:
    int cal(vector<int>& nums, int k, int height) {
        int i, j;
        for(i = k-1;i >= 0;i--) 
            if(nums[i] < height)  break;
        for(j = k+1;j < nums.size();j++)
            if(nums[j] < height)  break;
        return (j-i-1)*height;
    }

    int maximumScore(vector<int>& nums, int k) {
        vector<int>arr = nums;
        sort(arr.begin(), arr.end());
        auto it = unique(arr.begin(), arr.end());
        arr.erase(it, arr.end());
        int ans = -1;
        for(int h : arr) {
            cout << h << " " << endl;
            if(h > nums[k])  break;
            ans = max(ans, cal(nums, k, h));
        }
        return ans;
    }
};