P9397 「DBOI」Round 1 DTTM 题解

AssassinQ · 2023-06-09 13:50:25 · 题解

题目传送门

• 让我们先来翻译题目意思：

1. 一个平面直角坐标系中共有 n 个点，每两个点连成一条线段且所有线段互不相交。

2. 每条线段两个端点的横坐标差的和尽量小。

3. 无法满足条件的数据输出 -1。

4. 最重要的是：数据范围 n 最大为 5\times10^5。

• 考虑算法时间复杂度： O(n) / O(n \log n)

开始构造算法：

首先考虑 -1 的情况，易得当点数 n 为奇数时，无法实现题目所要求的“所有线段互不相交”。

再考虑当 n 为偶数时答案最小如何实现，画几个点我们就可以发现：除平行于 y 轴 的线段之外，我们将所有的线段映射到 x 轴上，只有没有一线段的映射将另一线段的映射完全覆盖（既包含），那么答案一定是最小的。

既然如此，将每一个点分别按 x,y 轴从小到大连接，可以保证最终答案最小。

经验证，上述的贪心思路能保证每一条线段互不相交。

AC 代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAXN=5e5+5;
ll n,ans;
struct star{
    ll x,y,num;
}p[MAXN];
bool cmp(star a,star b){
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&p[i].x,&p[i].y);
        p[i].num=i;
    }
    if(n%2==0){
        sort(p+1,p+n+1,cmp);
        for(int i=1;i<=n;i+=2)
            ans+=p[i+1].x-p[i].x;
        printf("%lld\n",ans);
        for(int i=1;i<=n;i+=2) printf("%lld %lld\n",p[i].num,p[i+1].num); 
    }
    else printf("-1");
    return 0;
}