题解：P10224 [COCI 2023/2024 #3] Vrsar

· · 题解

题外话

建议评蓝，因为比 P9209 难

解题思路

首先看到 1\le n,m \le10^5 ，所以解决每个查询的时间最多只有 log{n} 的时间。我们可以发现，每次选择上山，都会额外花费一个 s 的时间下山，而如果我们直接去将要去的那座山就会节约这个 s ，所以我们会选择直接去最后要去的那座山也就是能呆的时间最长的那座山。

代码实现

首先看到 n,m \le 1000 ，可以使用 n^2 的算法，具体实现就是对于每个询问都一一计算出最大值，代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m;
struct node {
    int x, t, s;
    bool friend operator<(node a, node b) { return a.x < b.x; }
} dt[N];
int main() {
    freopen("vrsar.in", "r", stdin);
    freopen("vrsar.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x, t, s;
        cin >> x >> t >> s;
        dt[i] = { x, t, s };
    }
    sort(dt + 1, dt + n + 1);
    while (m--) {
        int k;
        cin >> k;
        int ans = 0;
        for (int i = 1; i <= n; i++) ans = max(ans, dt[i].t - abs(dt[i].x - k));
        cout << ans << " ";
    }
    return 0;
}

这个代码可以通过 44 分，也就是 63\% 的数据，所以需要优化，这里就衍生出两种做法，一种在线一种离线。

离线做法

可以发现滑雪时间 T=t[i]-abs(x[i]-d) 所以分两段考虑，先给所有 d 排序，在 d 前面计算距离为 T=t[i]-x[i]+d 都有 t[i]-x[i] 所以考虑存这个东西，可以使用 set 来快速实现，在 d 后面的也同理，代码如下：

#include<bits/stdc++.h>
#define PII pair<int,int>
#define wz first
#define id second
using namespace std;
const int N=2e5+10;
int n,m;
struct node{
    int x,t,s;
    bool friend operator<(node a,node b){
        return a.x<b.x;
    }
}dt[N];
set<int> st,st1;
PII qu[N];
int ans[N];
int main(){
//  freopen("vrsar.in","r",stdin);
//  freopen("vrsar.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x,t,s;
        cin>>x>>t>>s;
        dt[i]={x,t,s};
    }
    st.insert(1e9+10);
    st1.insert(1e9+10);
    sort(dt+1,dt+n+1); 
    for(int i=1;i<=n;i++)
        st.insert(-(dt[i].t-dt[i].x));
    for(int i=1;i<=m;i++){
        cin>>qu[i].wz;
        qu[i].id=i;
    }
    sort(qu+1,qu+m+1);
    for(int i=1,j=1;i<=m;i++){
        while(dt[j].x<=qu[i].wz&&j<=n){
            st.erase(-(dt[j].t-dt[j].x));
            st1.insert(-(dt[j].t+dt[j].x));
            j++;
        }
        ans[qu[i].id]=max(-*st.begin()+qu[i].wz,-*st1.begin()-qu[i].wz);
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<" ";
    return 0;
}
//瓶颈：找相减最大时间
//63pts
//如何优化？ 
//t=dt[i].t-abs(dt[i].x-k)
//t=dt[i].t-dt[i].x+k(dt[i]>k)
//t=dt[i].t+dt[i].x-k(dt[i]<k)
//set优化nlogn
//100pts
在线做法

同样的思路，关键在于快速查询，看到区间，看到最大值，看到 log{n} 考虑线段树，但是十分繁琐，打了半小时没打出来放弃了 错误代码 ，也不知道会不会有人这么写。