G7016 [GESP202509 七级] 金币收集 题解

知识点：最长不降子序列、排序、模型转换。

解题思路

过滤t<x的不可达金币，按位置x再按t-x升序排序，对t-x求最长不降子序列。

为什么正确

只能向右以单位速度移动时，先后收集两枚金币要求x非递减且t-x非递减；反之可通过等待实现，问题等价为二维链。

易错点

要求不降，二分使用upper_bound；同位置的金币要按变换值升序，使可等待的顺序保留。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<pair<long long,long long>>a;
    for(int i=0;i<n;i++) {
        long long x,t;
        cin>>x>>t;
        if(t>=x)a.push_back({x,t-x});
    }
    sort(a.begin(),a.end());
    vector<long long>dp;
    for(auto [x,y]:a) {
        auto it=upper_bound(dp.begin(),dp.end(),y);
        if(it==dp.end())dp.push_back(y);
        else *it=y;
    }
    cout<<dp.size();
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。