「CF1237C」Balanced Removals

题意：给出 $n$ 个三维的点，每次可删除两个平衡的点，两个点平衡当且仅当三维空间中两个点内没有其他点，输出一种方案，$\frac{n}{2}$ 行，每行代表删除的两个点。

是一道排序的题。

很明显将三个维度都从小到大排序，那么把前面的维度都比较完后，在比较最后一个维度时相邻的两个点中间肯定是没有其他点的。

关键在如何比较前面的维度，首先排序，我们一维一维的来比较，把这一维中坐标相同的递归入下一维，由于已经排好序，所以保证正确性。

但是这种方法不能保证把在所有的点删完，所以我们再拿一个数组标记是否删除，在递归后回溯时重新遍历一遍是否有没被标记的数，删除即可。

思路来自一位大佬沉迷学习的LJY。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,flag[50101];
struct node
{
	int x;
	int y;
	int z;
	int id;
}a[50101];
int cmp(node a,node b)
{
	if(a.x!=b.x)
		return a.x<b.x;
	else
	{
		if(a.y!=b.y)
			return a.y<b.y;
		else
			return a.z<b.z;
	}
}
int change(int i,int p)
{
	if(p==0)
		return a[i].x;
	else if(p==1)
		return a[i].y;
	else
		return a[i].z;
}
void solve(int l,int r,int now)
{
	if(now==2)
	{
		for(int i=l;i<r;i+=2)
		{
			printf("%d %d\n",a[i].id,a[i+1].id);
			flag[i]=flag[i+1]=1;
		}
		return ;
	}//比较到最后一维，说明前2维都相同，直接输出
	int i,j;
	i=j=l;
	while(i<=r)
	{
		while(j<r&&change(i,now)==change(j+1,now))
			j++;//找出第now维全部相同的区间，进入下一维
		solve(i,j,now+1);
        j++;
        i=j;
	}
	i=l;
	while(i<=r)
	{
		while(i<=r&&flag[i])
			i++;
		if(flag[i])
			return ;
		j=i+1;
		if(j>r)
			return ;
		while(j<r&&flag[j])
			j++;
		if(flag[j])
			return ;
		flag[i]=flag[j]=1;
		printf("%d %d\n",a[i].id,a[j].id);
		i=j+1;//剩下的直接输出
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
		a[i].id=i;
	}
	sort(a+1,a+n+1,cmp);
	solve(1,n,0);
	return 0;
}

标准做法其实是差不多的，就是这个思路：

先来考虑一下二维时的情况，那么对于 $x$ 相同的点，我们按 $y$ 排序，然后相邻的一对对消除，最后 $x$ 坐标相同的点最多剩下一个，那么此时所有点的 $x$ 坐标都不一样，再按 $x$ 把 $x$ 相邻的一对对删除即可，扩展到三维，显然也可以同样的思路，先把 $x,y$ 相同的点按 $z$ 一对对消除，然后在把 $x$ 相同的点按 $y,z$ 相邻的一对对消除，最后按 $x,y,z$ 相邻的一对对消除即可。

网上的代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int N=5e4+7;
int n;
struct dat {
    int x,y,z,id;
    inline bool operator < (const dat &tmp) const {
        if(x!=tmp.x) return x<tmp.x;
        return y!=tmp.y ? y<tmp.y : z<tmp.z;
    }
}A[N];
bool vis[N];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        A[i].x=read(),A[i].y=read(),A[i].z=read(),A[i].id=i;
    sort(A+1,A+n+1);
    int l=1;
    for(int i=2;i<=n;i++)
        if(l && A[i].x==A[l].x && A[i].y==A[l].y)
        {
            vis[i]=vis[l]=1;
            printf("%d %d\n",A[i].id,A[l].id);
            l=0;
        }
        else l=i;
    l=1; while(vis[l]) l++;
    for(int i=l+1;i<=n;i++)
    {
        if(vis[i]) continue;
        if(l && A[i].x==A[l].x)
        {
            vis[i]=vis[l]=1;
            printf("%d %d\n",A[i].id,A[l].id);
            l=0;
        }
        else l=i;
    }
    l=1; while(vis[l]) l++;
    for(int i=l+1;i<=n;i++)
    {
        if(vis[i]) continue;
        if(l) printf("%d %d\n",A[i].id,A[l].id),l=0;
        else l=i;
    }
    return 0;
}