2022杭电多校第三场 K题 Taxi

题目链接

Taxi

题目大意

给定我们二维平面上的$n$个点，我们从当前点$(x,y)$，前往第$i$个点，会减少花费$min((|x-x_i|+|y-y_i|),w_i)$，给定我们$q$个询问，每次给我们一个二维平面上的一个点，我们需要计算出最大的减少的花费。

题解

主要用到了一个神奇的转换，我也没遇到过，比赛的时候我队友告诉我的~

我们需要预处理出来所有点的四个最值，这样计算的时候就可以$O(1)$的时间计算出来了。
我们根据每个点的$w$值从小到大进行排序，然后二分标号，然后计算出来当前的最大距离$d$，通过$d$和$w$进行判断，下一步去左边还是右边，需要注意的是我们需要在二分过程中记录最值。具体细节看代码，看代码会好理解一些。

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
const int maxn = 100010, inf = 1e18;
typedef struct node
{
    
    int x, y, w;
    bool operator < (const struct node &t) const{
    
        return w < t.w;
    } 
}Node;
Node points[maxn];
int a[maxn], b[maxn], c[maxn], d[maxn];
int n, q;
int sx, sy;
int res;
bool check(int mid)
{
    
    int t = -inf;
    int w = points[mid].w;
    t = max(t, sx + sy + a[mid]);
    t = max(t, sx - sy + b[mid]);
    t = max(t, -sx + sy + c[mid]);
    t = max(t, -sx - sy + d[mid]);
    res = max(res, min(w, t));
    return w <= t;
}
signed main()
{
    
    IOS;
    int t; cin >> t;
    while(t --){
    
        cin >> n >> q;
        for(int i = 0; i < n; i ++){
    
            int x, y, w; cin >> x >> y >> w;
            points[i] = {
    x, y, w};
        }
        sort(points, points + n);
        a[n] = b[n] = c[n] = d[n] = -inf;
        for(int i = n - 1; i >= 0; i --){
    
            a[i] = max(a[i + 1], -points[i].x - points[i].y);
            b[i] = max(b[i + 1], -points[i].x + points[i].y);
            c[i] = max(c[i + 1], points[i].x - points[i].y);
            d[i] = max(d[i + 1], points[i].x + points[i].y);
        }
        while(q --){
    
            res = -inf;
            cin >> sx >> sy;
            int l = 0, r = n - 1;
            while(l < r){
    
                int mid = l + r + 1 >> 1;
                if(check(mid)) l = mid;
                else r = mid - 1;;
            }
            check(l);
            cout << res << endl;
        }
    }
    return 0;
}