题解 | #采集灵石#

题目传送门

这道题目的主要思维是贪心算法，十分的简单， 第一题到第二题之间的难度。

首先肯定先定义变量和输入。

这里我定义数组时用得是 变量（当然 也可以），然后输入：

const int N=1e6+10;
long long n,k;
pair<long long,long long> a[N];

cin>>n>>k;
for(long long i=1;i<=n;i++)
{
	cin>>a[i].second>>a[i].first;
}

有些智慧的人应该也注意到了这个代码是先输入 再输入的 ，具体用意后面会讲。

接下来就是实践贪心算法。

那我们是对什么变量进行排序呢？

首先题目上说“玩家可以耗费 (也就是 ) 块灵石从任意一个其他浮岛或初始平台前往第 个浮岛。”，那么我们肯定是对 进行排序。

sort(a+1,a+n+1);

这里就要说到刚刚输入的用意了，因为对 进行排序，默认的是对 进行排序，楼主也懒得写 函数，所以我用 定义变量并先输入 再输入的 。

然后就很简单了。为了让最后 最多， 肯定要大于 , 肯定也要大于等于 ,上代码。

for(long long i=1;i<=n;i++)
{
	if(k>=a[i].first&&a[i].second>a[i].first)
	{
		k-=a[i].first;
		k+=a[i].second;
	}
}

最后一个简单的输出。

cout<<k;

完美结束，完整程序就不上了，以防有人 +。