小埋公司的IPO方案的题解

目录

原题描述：

题目描述

输入格式

输出格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

题目大意：

主要思路：

但是but

代码code：

---

原题描述：

题目描述

小埋创建的公司即将开始IPO。为了更高的将价格将股票卖给风险投资公司，小埋希望在 IPO 之前公司开展一些项目增加自己的公司资本。由于资源有限，它只能在 IPO 之前完成最多??个不同的项目。请帮助小埋设计完成最多 ?个不同的项目后得到的最大总资本的方式。

小埋有这样??个项目。对于每个项目 i ，它都有一个纯利润??,和启动该项目需要的最小资本?。

最初，小埋的资本为?。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本当中。

总而言之，从这??个项目当中选择最多??个不同的项目列表，以最大化最终的资本，并输出最终可获得的最多的资本。

输入格式

第一行输入一个整数?。

以下??行有??个项目，每一行有两个值??，的值是投资获取的利润，的值是启动该项目的最小资本。

输出格式

输出一个整数，输出最大化后的资本。

输出格式

输出一个整数，输出最大化后的资本。

样例 #1

样例输入 #1

3 0 2
1 0
2 1
3 1 

样例输出 #1

4

样例 #2

样例输入 #2

3 0 3 
1 0 
2 1
3 2

样例输出 #2

6

提示

题目大意：

这个好理解，就是和解锁关卡一样，你最多可以解锁k个，解锁第i个关卡需要的经验值（解锁不消耗经验值，也就是不用-）如果你解锁了第i个关卡，你会获得的经验值，你初始有的经验值，有n个关卡。

主要思路：

很明显，这题就是贪心，每次找到比w小的项目，把这个项目获得的钱放进优先队列中（如果有了就不放），找到获得钱数最大的（q.top)然后弹出队首，w+=q.top()。

但是but

可是这样做还是会超时，因为每次找比w小的项目要花n的复杂度，所以会超时。

这个时候。。。

双指针闪亮登场。

我们可以先按照需要的钱从小到大的排个序，由于每次w会再增大，所以可以用pos记入到哪了，每次从pos开始找，复杂度就会小很多。

代码code：

#include<bits/stdc++.h>
using namespace std;
int n,w,k;
priority_queue<int> q;
pair<int,int> p[100010];
int main()
{
	cin>>n>>w>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>p[i].second>>p[i].first;//反着存，方便sort
	}
	sort(p+1,p+1+n);
	int p1=1;
	int cnt=0;
	while(k--)
	{
		while(p1<=n&&p[p1].first<=w)//双指针
		{
			q.push(p[p1].second);
			p1++;
		}
		if(q.empty())//如果空了，就跳出。
		{
			break;
		}
		w+=q.top();
		q.pop();//加上，pop()
//		w-=tmp;
		
//		cnt+=tmp;
	}
	cout<<w;
	return 0;
}