题解：P14078 [GESP202509 七级] 金币收集

· · 题解

题解：P14078 [GESP202509 七级] 金币收集

题目传送门

题外话

我用伪 O(n^2) 的做法在 GESP 考场上喜提 22.5 分，但在洛谷上提交居然得了满分。居然这道题是一道绿题，有点惊讶。毕竟我的做法是贪心，感觉最多只值黄题难度。差点就场切绿题了。

思路

我们需要刚好在第 t_i 秒如果在 x_i 的坐标就可以吃到这个金币，首先因为我们只能从左往右走，所以我们会想到按照 x_i 坐标来进行排序，此时我们走到那儿时如果之前从没有原地不动会发现我们还需要等待 t_i-x_i 时间吃到该金币，所以在我们等到那个时间时我们会浪费掉 t_i-x_i 的时间，所以有些金币在等待后是吃不到了。那我们需要预处理每个金币在等待多久之后吃不到了，很简单，那就是拿一个数组 p 存储 t_i-x_i 即可。我们想吃到更多的金币那就找 p 的最长上升子序列，因为我从前往后每个金币都保证一个金币浪费的时间永远会影响到后面的金币。

小提示：

  1. 当 x_i 相同时需要按照 t_i 从小往大排序。不然 x_i 相同时前面的 p_i 会影响到后面的 p_j。
  2. 注意 t_i < x_i 的情况。
  3. 最长上升子序列需要用二分优化到可以实现 n \le 10^5 做法。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct pp{
    int a,b;
}a[230000];
int p[230000],f[230000];
int cmp(pp ap,pp bp){
    if(ap.a==bp.a){
        return ap.b<bp.b;
    }
    return ap.a<bp.a;
}//排序
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].a>>a[i].b;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        if(a[i].a>a[i].b){
            p[i]=1e12;
        }//注意时间小于坐标
        else{
            p[i]=a[i].b-a[i].a;
        }
    }
    //最长上升子序列
    f[1]=p[1];
    int q=1;
    if(p[1]==1e12){
        f[1]=0;
        q=0;
    }
    for(int i=2;i<=n;i++){
        if(p[i]==1e12){
            continue;
        }
        int l=1,r=q,ans=-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(f[mid]>p[i]){
                r=mid-1;
                ans=mid;
            }
            else{
                l=mid+1;
            }
        }
        if(ans==-1){
            q++;
            f[q]=p[i];
        }
        else{
            f[ans]=p[i];
        }
    }
    cout<<q;
    return 0;
}