180竞赛

var maxPerformance = function(n, speed, efficiency, k) {
    const d = [];
    for (let i = 0; i < n; i++) {
        d.push({ s: speed[i], e: efficiency[i] });
    }
    d.sort((a, b) => b.e - a.e);
    let m = 0;
    let sumS = 0;
    let result = 0;
    let maxS = 0;
    let maxE = 0;
    const heap = [];
    var swap = function(x, y) {
        const t = heap[x];
        heap[x] = heap[y];
        heap[y] = t;
    }
    var up = function(index) {
        if (!index || heap[index] >= heap[Math.floor((index - 1) / 2)]) return;
        swap(index, Math.floor((index - 1) / 2));
        up(Math.floor((index - 1) / 2));
    }
    var down = function(index) {
        let max = index;
        max = heap[index * 2 + 1] < heap[max] ? index * 2 + 1 : max;
        max = heap[index * 2 + 2] < heap[max] ? index * 2 + 2 : max;
        if (max === index) return;
        swap(max, index);
        down(max);
    }
    for (let i = 0; i < n; i++) {
        if (i < k) {
            sumS += d[i].s;
            heap.push(d[i].s);
            up(i);
        } else if (d[i].s > heap[0]){
            sumS += d[i].s - heap[0];
            heap[0] = d[i].s;
            down(0);
        }
        if (sumS * d[i].e > m) {
            m = sumS * d[i].e;
            result = (sumS % 1000000007) * d[i].e % 1000000007;
            maxS = sumS;
            maxE = d[i].e;
        }
    }
    let rrr = 0;
    let ttt = 0;
    maxS = maxS % 1000000007;
    while (maxS) {
        let tt = maxS % 10;
        maxS = (maxS - tt) / 10;
        tt = tt * maxE % 1000000007;
        for (let i = 0; i < ttt; i++) {
            tt = tt * 10 % 1000000007;
        }
        rrr += tt;
        ttt++;
    }
    return rrr % 1000000007;
};

/**
 * @param {number} n
 * @param {number[]} speed
 * @param {number[]} efficiency
 * @param {number} k
 * @return {number}
 */
// 这个会超时，但也是目前唯一的解
var maxPerformance = function(n, speed, efficiency, k) {
    let arr = [];
    for(let i=0; i<n; i++){
        arr.push([speed[i], efficiency[i]])
    }
    // 按照效率从大到小
    arr.sort((a, b)=>b[1]-a[1]);
    let q = [];
    let res = 0, sum = 0;
    const insertSort = (arr, last)=>{
        let lIndex = arr.length-2;
        while(arr[lIndex]>last){
            arr[lIndex+1]= arr[lIndex]
            lIndex--;
        }
        if(arr[lIndex+1]!==last)
        arr[lIndex+1] = last
    }
    for(let i=0; i<n; i++){
        q.push(arr[i][0]);
        sum += arr[i][0];
        if(q.length > k){
            if(q.length == k+1) {
                 q.sort((a,b)=>a-b);
            }else {
                // 确保arr[i][0]是最后一个
                insertSort(q, arr[i][0])
            }
            
            sum -= q.shift();
        }
        // arr效率最小的, 可能是上面刚加进来的
        res = Math.max(res, sum * arr[i][1]);
        
    }
    return res%(10**9 + 7)
}


/*
// 其实我想得是这个循环取每一个数据时这个循环嵌套得次数是不定的。这中问题。难道这种问题普遍能用队列解决吗？反正拼接字符串不靠谱。往队列里面放数据，达到某个条件再从队列中去除某个数据。
// 我当时想的效率高它表现值也不一定最高，速度快表现值也不一定最高。那它两就没关系，所以要都遍历一遍找出最大的。
// 由最多 k 个工程师组成, 也可能小于 k;
var maxPerformance = function(n, speed, efficiency, k) {
    // 从 n个数据中取k个元素，fn(...k) 最大。
    let ak = [];
    for(let i=0; i<k; i++){
        ak[i] = i
    }
    let res = Infinity;
    
    
    let min = Infinity;
    let sspeed = ak.reduce((init, val)=>init+speed[val],0);
    ak.forEach(a=>{
        if(efficiency[a]<min){
            min = efficiency[a];
        }
    })
    res = Math.min(res, sspeed*min)
   
    
    return res%(10**9 + 7)
};
*/