CodeForces 577E Points on Plane(莫隊思維題)

題目描述

On a plane are nn points ( x_{i}xi​ , y_{i}yi​ ) with integer coordinates between 00 and 10^{6}106 . The distance between the two points with numbers aa and bb is said to be the following value:  (the distance calculated by such formula is called Manhattan distance).

We call a hamiltonian path to be some permutation p_{i}pi​ of numbers from 11 to nn . We say that the length of this path is value .

Find some hamiltonian path with a length of no more than 25×10^{8}25×108 . Note that you do not have to minimize the path length.

輸入輸出格式

輸入格式：

The first line contains integer nn ( 1<=n<=10^{6}1<=n<=106 ).

The i+1i+1 -th line contains the coordinates of the ii -th point: x_{i}xi​ and y_{i}yi​ ( 0<=x_{i},y_{i}<=10^{6}0<=xi​,yi​<=106 ).

It is guaranteed that no two points coincide.

輸出格式：

Print the permutation of numbers p_{i}pi​ from 11 to nn — the sought Hamiltonian path. The permutation must meet the inequality .

If there are multiple possible answers, print any of them.

It is guaranteed that the answer exists.

輸入輸出樣例

輸入樣例#1：

5
0 7
8 10
3 4
5 0
9 12
      

輸出樣例#1：

4 3 1 2 5 
      

說明

In the sample test the total distance is:

(|5-3|+|0-4|)+(|3-0|+|4-7|)+(|0-8|+|7-10|)+(|8-9|+|10-12|)=2+4+3+3+8+3+1+2=26(∣5−3∣+∣0−4∣)+(∣3−0∣+∣4−7∣)+(∣0−8∣+∣7−10∣)+(∣8−9∣+∣10−12∣)=2+4+3+3+8+3+1+2=26

題意：定義曼哈頓距離為兩點之間x坐标差的絕對值與y坐标差的絕對值，在定義哈密頓路徑為所有相鄰兩點間的曼哈頓距離之和，給出一些點的xy坐标，求一個點排列使哈密頓路徑小于25*1e8

題解：

首先看到點的xy坐标均在1e6以内，然後如果按照直接優先x再y的順序排序，隻需要一組x坐标1-5e5的資料，每個x坐标的y坐标為1e6和0，然後距離就被卡到了5e11。

雖然上面的思想有錯誤，但是是有借鑒意義的，如果将哈密頓路徑了解為複雜度，長度了解為變量，這顯然是n^2的，然後你會想到一些優化的方法，比如說莫隊。

然後就可以根據莫隊的思想将x坐标分塊，分成0-999,1000-1999……的1000塊，每塊裡按照y從小到大的順序排序，這樣子塊内y是單調遞增的，最多增大1e6，x就算上下亂跳，也最多變化1e3*1e3=1e6，總變化最多2e9

但是還是有點鍋，就是塊與塊之間切換的時候，如果是從最大y切到下一坐标最小y，最多要跳1e6，總變化會多增加1e9

是以按照一個塊y遞增，下一個塊y遞減的順序排列，這樣子就穩了

代碼如下：

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

struct node
{
    int x,y,kd;
};

vector<node> g[1010];
int n;

int cmp1(node x,node y)
{
    return x.y<y.y;
}

int cmp2(node x,node y)
{
    return x.y>y.y;
}

int main()
{
    node tmp;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&tmp.x,&tmp.y);
        tmp.kd=i;
        g[tmp.x/1000].push_back(tmp);
    }
    for(int i=0;i<=1000;i++)
    {
        if(i&1)
        {
            sort(g[i].begin(),g[i].end(),cmp1);
        }
        else
        {
            sort(g[i].begin(),g[i].end(),cmp2);
        }
    }
    for(int i=0;i<=1000;i++)
    {
        for(int j=0;j<g[i].size();j++)
        {
            printf("%d ",g[i][j].kd);
        }
    }
}