优先队列 - big先

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了优先队列 - big先，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1601字，纯文字阅读大概需要3分钟。

内容图文

优先队列

优先大的元素出，或者优先小的元素出

https://blog.csdn.net/yuewenyao/article/details/88764046

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
vector<long long> s, s1, e, e1;
void sort(int left, int right);
bool cmp(int wl, int hl, int i);
priority_queue<long long> q;
long long ee = 1e+9 + 7;


int main()
{
    int n(0), k(0);
    cin >> n >> k;
    for(int i = 0; i < n; i++) 
    {
        int tmp1(0);
        cin >> tmp1;
        s.push_back(tmp1);
        // s1.push_back(tmp1);
    }
    for(int i = 0; i < n; i++) 
    {
        int tmp2(0);
        cin >> tmp2;
        e.push_back(tmp2);
        // e1.push_back(tmp2);
    }
    int len = e.size();
    sort(0, len-1);
    // for(int i = 0; i < e.size(); i++) cout << e[i] << " ";
    // cout << endl;
    long long sum = 0;
    long long ans = 0;
    for(int i = 0; i < len; i++) // 从效率最高的工人降序选择，第一次只能选	一个，然后两个，三个，...，k个（最多），这个时候用优先队列来进行维护
    {
        sum += s[i];
        q.push(-s[i]);  // 填入负值是和上一个sum语句相关的
        while(q.size() > k)  // 保证最低效率情况下能获得最高的速度
        {
            sum += q.top();
            q.pop();
        }
        ans = max(ans, sum*e[i]);

    }
    // cout << ee << endl;
    cout << ans%ee;
    return 0;
}


void sort(int left, int right)  
{
if(left >= right) return;

int i = left;
int j = right;
int wl = s[left];
int hl = e[left];
while(i < j)
{
    // cout << i << " " << j << " " << left << endl;
    while(i < j && cmp(wl, hl, j)) j--;
    s[i] = s[j];
    e[i] = e[j];

    while(i < j && !cmp(wl, hl, i)) i++;
    s[j] = s[i];
    e[j] = e[i];
}
// cout << 1 << endl;
s[i] = wl;
e[i] = hl;
sort(left, i-1);
sort(i+1, right);
}
bool cmp(int wl, int hl, int i)
{
    // if(wl < w[i]) return true;
    // if(wl > w[i]) return false;
    if(hl > e[i]) return true;
    else return false;
}

内容总结

以上是互联网集市为您收集整理的优先队列 - big先全部内容，希望文章能够帮你解决优先队列 - big先所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---