力扣算法篇：IPO（首次公开募股）

题解：每次选最大 超时

class Solution {
public:int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {//n个项目中选k个使得资本最大化 每次在w>=capital[i]中选择纯利润最大的 int n = capital.size();//用一个数组标志该项目是否选过vector<int> flag(n,0);int maxprofit;int maxNum;for(int x = 1;x<=k;x++){//每次选择都需要考虑到无法投资的情况maxNum = -1;maxprofit = -1;for(int i = 0;i<n;i++){//该项目未选 并且可以投资 利益最大if(flag[i]==0 && w>=capital[i]&&profits[i]>maxprofit){maxprofit = profits[i];maxNum = i;}}//出来的时候就是利润最大的项目 更改w和flag 注意避开资本在剩余项目中一个项目都无法投资的情况if(maxNum!=-1){w+=profits[maxNum];flag[maxNum] = 1;}else{//没有可选项目了 退出break;}}return w;}
};

更改：
先将项目根据投资资本排序，然后使用优先队列（纯利润降序队列）选择最大利润
优先队列具有队列的所有特性，包括队列的基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的。

class Solution {
public:int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {//n个项目中选k个使得资本最大化 每次在w>=capital[i]中选择纯利润最大的 int n = profits.size();//项目id数组vector<int> id(n,0);for(int i = 0;i<n;i++){id[i] = i;}//id数组根据投资资本排序 递增序列sort(id.begin(),id.end(),[&](int a,int b){return capital[a]<capital[b];});//优先队列 降序队列 大顶堆priority_queue<int,vector<int>,less<int>> q;int j = 0;//外循环遍历k次选取项目for(int i = 0;i<k;i++){//选择投资资本低于w的项目加入优先队列for(;j<n&&capital[id[j]]<=w;j++){q.push(profits[id[j]]);}//队列为空则说明无项目可选if(q.empty()){break;}//否则 选中队头项目(纯利润最大) 更改ww+=q.top();q.pop();}return w;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！