题解 | #采集灵石#

题目传送门

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

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

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

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;
}

有些智慧的人应该也注意到了这个代码是先输入 $a[i].second$ 再输入的 $a[i].first$ ，具体用意后面会讲。

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

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

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

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

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

然后就很简单了。为了让最后 $k$ 最多， $a[i].second$ 肯定要大于 $a[i].first$ , $k$ 肯定也要大于等于 $a[i].first$ ,上代码。

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;

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