【CodeForces】576 C. Points on Plane

【题目】C. Points on Plane

【题意】给定坐标系中n个点的坐标（范围[0,10^6]），求一种 [ 连边形成链后总长度<=2.5*10^9 ] 的方案。n<=10^6。

【算法】思维题（分块思想）

【题解】将这个10^6*10^6的矩阵划分为1000个10^3*10^6的矩阵，第奇数个矩阵内部按y升序连边，第偶数个矩阵内部按y降序连边，两个矩阵之间就直接连边。

1.到达每个点横坐标要移动10^3，总距离10^9。

2.每个矩阵内部纵坐标要移动10^6，总距离10^9。

3.矩阵之间的连边，每次最长2*10^3，总距离2*10^6。

所以总距离为2*10^9+2*10^6，满足要求。

排序的实现和分块类似，复杂度O(n log n)。

#include<cstdio>

#include<cctype>

#include<algorithm>

using namespace std;

int read(){

    char c;int s=,t=;

    while(!isdigit(c=getchar()))if(c=='-')t=-;

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s*t;

}

const int maxn=;

struct cyc{int x,y,id;}a[maxn];

int n;

bool cmp(cyc a,cyc b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}

int main(){

    n=read();

    for(int i=;i<=n;i++){

        a[i].x=read()/;

        a[i].y=read();

        if(a[i].x%)a[i].y=-a[i].y;

        a[i].id=i;

    }

    sort(a+,a+n+,cmp);

    for(int i=;i<=n;i++)printf("%d ",a[i].id);

    return ;

}

巴特西

【CodeForces】576 C. Points on Plane

最新文章

热门文章