算法
(排序、暴力枚举) $O(n\log n)$
可以用 vector<pair<long long, int>>
来维护每个朋友的信息,即朋友所在的位置,以及他可以给 $Taro$ 的钱,并对该数组进行排序。记 ans
为 $Taro$ 所能走到的位置,初始值为 $k$,然后检验每一个朋友的信息,对于当前的朋友的位置不超过 $ans$ 的话,则将这个朋友给的钱加进 $ans$ 里,然后接着检验下个朋友,直到当前朋友的位置超过 $ans$ 就结束该操作。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::max;
using std::pair;
using std::vector;
using ll = long long;
int main() {
int n;
ll k;
cin >> n >> k;
vector<pair<ll, int>> f(n);
rep(i, n) {
cin >> f[i].first >> f[i].second;
}
sort(f.begin(), f.end());
int j = 0;
ll ans = k;
while (j < n and f[j].first <= ans) {
ans += f[j].second;
j++;
}
cout << ans << '\n';
return 0;
}