P9397题解

· · 题解

原题链接

P9397 「DBOI」Round 1 DTTM

题目简述

现在星空中有 n 颗星星，每颗星星位于不同的坐标上，现在要满足以下两个要求：

  1. 每一颗星星都是且仅是一条线段的端点，所有线段互不相交（包括端点）。

  2. 所有线段左右端点 |x_l-x_r| 之和有最小值。

现在需要得到线段左右端点 |x_l-x_r| 之和的最小值以及连接方案，如果无解，就输出 -1。

解题思路

首先，我们考虑无解的情况，不难看出，如果 n 为奇数，那么是一定无解的，因为到最后必定会有一颗星星不能与其他星星连接，这时，直接输出 -1 即可。若 n 为偶数，则现将所有的星星按照 x 排序，如果 x 相等就继续按照 y 排序，最后只需要再讲将相邻的两个星星连线即可，这时就需要定义一个结构体：

struct node
{
    int x,y,id;
}a[1000010];

参考代码

#include<bits/stdc++.h>
using namespace std;
long long n,sum;
#define QwQ return 0;
struct node
{
    int x,y,id;
}a[1000010];
bool cmp(node a,node b)
{
    if(a.x==b.x)//如果两颗星星的x轴相等
        return a.y<b.y;//就继续比较y轴
    return a.x<b.x;//否则直接比较x轴
}
int main()
{
    cin>>n; 
    if(n%2)//如果星星的数量为奇数，那么就直接输出-1
    {
        cout<<-1<<endl;
        return 0;
    }
    for(int i=0;i<n;i++)
    {
        cin>>a[i].x>>a[i].y;//输入每个星星的x轴以及y轴
        a[i].id=i+1;//定义每颗星星的编号
    }
    sort(a,a+n,cmp);//将星星按照顺序排序
    for(int i=0;i<n;i+=2)
        sum+=a[i+1].x-a[i].x;//让相邻两颗星星的x相减，使其最小
    cout<<sum<<endl;//输出这个最小值
    for(int i=0;i<n;i+=2)
        cout<<a[i].id<<" "<<a[i+1].id<<endl;//输出这两颗星星的编号
    QwQ;//华丽的结束
}//clbzdq