【15843】小埋公司的IPO方案题解

嘿嘿,依然不想排版


解题思路

该题要求资本的最大值,那么考虑贪心操作。只要我们选择前K个净利润最大的启动资金小于W的项目那么就可以轻松完成该要求。

核心代码

//pq为优先队列,arr是包含int a,b的结构体
//输入方式:cin>>n>>ret>>k;  cin>>arr[i].a>>arr[i].b;
    sort(arr+1,arr+n+1,cmp);
	p=1;
	for(long long i=1;i<=k;i++){
		while (p<=n && arr[p].b<=ret){
			pq.push(arr[p].a);
			p++;
		}
		if(pq.empty()){
			break;
		}
		ret+=pq.top();
		pq.pop();
	}