2022 Hangzhou Electric Power Multi-School Session 3 K Question Taxi

题目链接

Taxi

题目大意

Given our two-dimensional plane$n$个点,We are from the current point$(x,y)$,前往第$i$个点,Can reduce the cost$min((|x-x_i|+|y-y_i|),w_i)$,给定我们$q$个询问,Every time give us a 2 d plane of a point,We need to calculate the maximum to reduce the cost of.

题解

Mainly with the help of a magical transformation,我也没遇到过,Game when my teammates told me~

We need pretreatment out all points of the four most value,When calculated in this way can$O(1)$Time was calculated.
We according to each point$w$值从小到大进行排序,Then the binary label,Then calculate the maximum distance$d$,通过$d$和$w$进行判断,The next step to the left or right,It's important to note that we need to record the value in the process of binary.具体细节看代码,See the code will understand some.

代码

#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;
}