采集灵石

https://ac.nowcoder.com/acm/problem/229311

题目描述

牛牛打开了一个有趣的游戏。在游戏中，灵石是一种非常重要的资源。每位玩家每天有且仅有一次采集的机会。 灵石会在许多浮岛上刷新，每个浮岛上灵石刷新数量可能不同。这些浮岛之间通过传送法阵相连，激活每个岛屿上的传送法阵花费的灵石数量也不同。玩家可以耗费 mi块灵石从任意一个其他浮岛或初始平台前往第 i 个浮岛。采集完毕后玩家可以从任何浮岛直接退出地图。 现在，牛牛手中有着 K 块灵石，他想知道自己今天采集结束后最多能拥有多少块灵石。牛牛只能在周末玩一小时游戏，他希望你能编写一个程序帮他及时算出来。

输入描述

第一行两个正整数 N,K 分别表示浮岛的数量和牛牛手中初始的灵石数量。 接下来 N 行，每行两个正整数ki,mi，第 i 行的正整数 ki表示第 i 个浮岛上今日刷新的灵石数量, mi表示传送到第 i 个浮岛所需的灵石数量。

输出描述

一个正整数，表示牛牛今天采集后最多能拥有的灵石数量。

-—————————————————————————————————————

题意理解

• 1.每个浮岛有2个数据：mi,ki。->可使用pair 或者 struct进行存储；

• 2.要采集尽可能多的灵石->贪心->按照所需支付灵石数量从小到大排序；

• 3.要使灵石数量K正增长->需要ki>m1;

分段实现

step1：输入数据

• 1.输入浮岛总数n；

• 2.循环n次，输入ki,mi； （使用pair数据结构存储，先输入ai.second（ki）,则ai.first为mi（后续代码排序时，按照需要支付的灵石数量mi从小到大排序，避免过早结束采集） =>pair数据结构默认按照a[i].first排序；

step2：排序:使用sort()函数直接排序，默认按照ai.first从小到大排序；

step3：循环采集：要让灵石数量K持续正增长，才能满足K的值取最大；

满足mi<ki的浮岛采集后会让K正增长，且当前灵石数量K>mi时才能采集；

step4 : 输出灵石数量K；

整体代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
pair<int,int> a[N];
int main(){

int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i].second>>a[i].first;	
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		if(a[i].second-a[i].first>0 and k>=a[i].first) k=k-a[i].first+a[i].second;
	}
	cout<<k;
	return 0;
}