自动搬运

查看原文

来自洛谷，原作者为

	wmrqwq 会登顶的。

搬运于2025-08-24 22:47:59，当前版本为作者最后更新于2023-07-29 10:38:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题链接

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