京东4.18 笔试

1.最小亏损的题目,最后提交的,第一次排序超时,过了50%,换成大顶堆
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
void getMinloss(priority_queue<int>losData,int m,int n, int q){
    int res=0;
    int day=q/m,lis=q%m;
    if(lis>0)
        day=day+1;
    if(q==n){
        for (int i = 1; i <=day; ++i) {
            for (int j = 0; j < m; ++j) {
                res+=i*losData.top();
                losData.pop();
                if(losData.empty())
                    break;
            }
        }
    } else{
        for (int k = 0; k <n-q; ++k){
            losData.pop();
        }
        for (int i = 1; i <=day; ++i) {
            for (int j = 0; j < m; ++j) {
                res+=i*losData.top();
                losData.pop();
                if(losData.empty())
                    break;
            }
        }
    }
    cout<<res<<endl;
}
int main() {
    int n,m,q;
    cin>>n>>m;
    priority_queue<int> losData;
    int temp;
    for (int i = 0; i <n ; ++i) {
        cin>>temp;
        losData.push(temp);
    }
    cin>>q;
    vector<int> qData;
    for (int j = 0; j < q; ++j) {
        cin>>temp;
        qData.push_back(temp);
    }
    for (int k = 0; k <q; ++k) {
        int s=qData[k];
        getMinloss(losData,m,n,s);
    }
    return 0;
}

#京东##笔试题目#
全部评论
这是ac了吗
点赞 回复 分享
发布于 2020-04-18 21:57
时间复杂度为O(nlogn)吗
点赞 回复 分享
发布于 2020-04-19 00:07

相关推荐

07-02 13:52
武汉大学 golang
骗你的不露头也秒
牛客87776816...:😃查看图片
点赞 评论 收藏
分享
07-07 12:47
门头沟学院 Java
码农索隆:竟然还真有卡体检报告的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务