网站建设好后怎样形成app,未备案网站,百度正版下载,郑州有学网站制作1--项目的最大利润 题目描述#xff1a; 输入#xff1a;正数数组 costs#xff0c;costs[i] 表示项目 i 的花费#xff1b;正数数组 profits#xff0c;profits[i] 表示项目 i 的花费#xff1b;正数 k 表示只能串行完成最多 k 个项目#xff1b;m 表示拥有的资金…1--项目的最大利润 题目描述 输入正数数组 costscosts[i] 表示项目 i 的花费正数数组 profitsprofits[i] 表示项目 i 的花费正数 k 表示只能串行完成最多 k 个项目m 表示拥有的资金每完成一个项目后资金会立即更新原始资金 利润 输出求解最后获得的最大利润 主要思路 小根堆存储所有项目大根堆存储可以进行的项目 每次从小根堆解锁项目添加到大根堆中优先做大根堆利润最高的项目 #include iostream
#include vector
#include queuestruct project{project(int c, int p) : cost(c), profit(p) {}int cost;int profit;
};class cmp1{
public:bool operator()(project* a, project* b){return a-cost b-cost;}
};struct cmp2{bool operator()(project* a, project* b){return a-profit b-profit;}
};class Solution{
public:int findMaxCapital(int m, int k, std::vectorint costs, std::vectorint profits){std::priority_queueproject*, std::vectorproject*, cmp1 minCostQ;std::priority_queueproject*, std::vectorproject*, cmp2 maxProfitQ;// 按cost按从小到大排序项目for(int i 0; i profits.size(); i){minCostQ.push(new project(costs[i], profits[i]));}for(int i 0; i k; i){while(!minCostQ.empty() minCostQ.top()-cost m){// 可以解锁新的项目maxProfitQ.push(minCostQ.top());minCostQ.pop();}if(maxProfitQ.empty()) return m; // 无法解锁新的项目直接返回// 更新资金m maxProfitQ.top()-profit;maxProfitQ.pop();}return m;}
};int main(int argc, char *argv[]){int m 1;int k 2;std::vectorint costs {1, 1, 2, 2, 3, 4};std::vectorint profits {1, 4, 3, 7, 2, 10};Solution S1;int res S1.findMaxCapital(m, k, costs, profits);std::cout res std::endl;
}
2--数据流的中位数 主要思路 分别使用大根堆和小根堆存储数据每添加一个数据先将数据添加至大根堆再将数据弹出并添加到小根堆 当小根堆值的数量与大根堆值的数量相差 2 时从小根堆弹出数据添加到大根堆中保持两个根堆的容量差不超过 根据添加数据量是偶数还是奇数返回对应的中位数 #include iostream
#include queueclass MedianFinder {
public:MedianFinder() {}void addNum(int num) {maxQ.push(num);minQ.push(maxQ.top());maxQ.pop();if(minQ.size() - maxQ.size() 1){maxQ.push(minQ.top());minQ.pop();}}double findMedian() {// 奇数if((maxQ.size() minQ.size()) % 2 ! 0) return minQ.top();// 偶数else return( (maxQ.top() minQ.top()) / 2.0);}
private:std::priority_queueint, std::vectorint, std::greaterint minQ;std::priority_queueint, std::vectorint, std::lessint maxQ;
};int main(int argc, char *argv[]){MedianFinder S1;S1.addNum(1);S1.addNum(2);S1.addNum(3);S1.addNum(4);S1.addNum(5);double res S1.findMedian();std::cout res std::endl;
}
