题解 | K. 走地鸡学飞

K. 走地鸡学飞

注意到收益和限制都是常数，不随时间变化

我们定义走地鸡当前活动区间为 ，初始取

每次尝试往 和 的地方扩展升级，一直扩展到两边都不能扩展为止即可

由于 ，可将坐标离散化一下，方便后续扩展

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define fType ll
#define foreach(x, a, b) for (fType x = a, _end_ = b; x <= _end_; x++)
#define foreach_sub(x, a, b) for (fType x = a, _end_ = b; x >= _end_; x--)
#define tpl make_tuple

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    ll n, x;
    cin >> n >> x;

    vector<ll> dct;
    dct.reserve(n + 1);
    dct.emplace_back(0);

    vector<tuple<ll, ll, ll>> tk(n + 1);
    foreach (i, 1, n)
    {
        auto &[a, h, v] = tk[i];
        cin >> a >> h >> v;

        dct.emplace_back(a);
    }

    sort(dct.begin(), dct.end());
    dct.erase(unique(dct.begin(), dct.end()), dct.end());

    vector<pair<ll, ll>> b(dct.size() + 1);
    foreach (i, 1, n)
    {
        auto &[a, h, v] = tk[i];
        int id = lower_bound(dct.begin(), dct.end(), a) - dct.begin() + 1;

        b[id] = {h, v};
    }

    ll L = lower_bound(dct.begin(), dct.end(), 0) - dct.begin() + 1, R = L;
    while (1)
    {
        bool mdf = 0;
        if (L > 1 && x >= b[L - 1].first) mdf = 1, x += b[--L].second;
        if (R < dct.size() && x >= b[R + 1].first) mdf = 1, x += b[++R].second;

        if (!mdf) break;
    }

    cout << x << "\n";
    return 0;
}

扩展思考：如果每个地点可包含多个任务，且 可取 ，该怎么做呢？