C++(clang++ 11.0.1) 解法, 执行用时: 1676ms, 内存消耗: 116384K, 提交时间: 2023-06-26 18:23:10

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P pair<ll,ll>
int main(){
    ll n;cin>>n;
    vector<P>v1;
    for(int i=1;i<=n;i++){
        ll x,y;cin>>x>>y;
        v1.push_back({x,y});
    }
    vector<vector<P>>v2(5);
    for(int i=0;i<v1.size();i++){
       ll x=v1[i].first,y=v1[i].second;
        // -i 是保证曼哈顿 距离相等的 时候 先找到id 较小的数
       v2[0].push_back({x+y,-i});
       v2[1].push_back({x-y,-i});
       v2[2].push_back({-x+y,-i});
       v2[3].push_back({-x-y,-i});
    }
    for(int i=0;i<4;i++){
        sort(v2[i].begin(),v2[i].end());
    }
    bool st[n];
    memset(st,0,sizeof(st));
    ll x1=0,y1=0,ans=0;
    for(int i=1;i<=n;i++){
        ll c=-1,d=-1;
        for(int j=0;j<4;j++){
    
            while(st[-v2[j].back().second]){
                v2[j].pop_back();
            }
            
            ll cj=-v2[j].back().second;
            ll dj=abs(x1-v1[cj].first)+abs(y1-v1[cj].second);
            
            if(dj>d||(dj==d&&cj<c)){
                c=cj;d=dj;
            }
        }
        ans+=d;
        st[c]=1;
        x1=v1[c].first;y1=v1[c].second;
    }
    cout<<ans<<endl;
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 884ms, 内存消耗: 51428K, 提交时间: 2023-06-24 12:38:14

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> vis(n);
    vector<pair<int, int>> a(n);
    vector p(4, vector<pair<int, int>>(n));
    for (int i = 0; i < n; i++) {
        auto &[x, y] = a[i];
        cin >> x >> y;
        p[0][i] = {x + y, -i};
        p[1][i] = {-x + y, -i};
        p[2][i] = {x - y, -i};
        p[3][i] = {-x - y, -i};
    }
    for (auto &i : p) sort(i.begin(), i.end());
    long long ans = 0, curx = 0, cury = 0;
    for (int i = 0; i < n; i++) {
        int id = 0, td = 0;
        for (int j = 0; j < 4; j++) {
            while (vis[-p[j].back().second]) p[j].pop_back();
            int dd = -p[j].back().second;
            int dis = abs(curx - a[dd].first) + abs(cury - a[dd].second);
            if (dis > td || (dis == td && id > dd)) {
                td = dis; id = dd;
            }
        }
        curx = a[id].first; cury = a[id].second;
        ans += td; vis[id] = 1;
    }
    cout << ans;
    return 0;
}