本文共 1879 字，大约阅读时间需要 6 分钟。

Utopia Divided

题目链接：

题目大意

在一个坐标系中，一个点一开始在原点，然后被要求每次走到一个规定的象限内。

要你输出任意一种合法方案，如果没有方案就输出 0。

思路

这道题我们可以用贪心的思想来做。

我们考虑让 $x,y$ 轴分开。

按假设现在是正的，你要改成负的（或者负的改成正的），那你就要加或减一个比当前坐标绝对值大的数。

那如果跟原来一样，那你可能有两个选择。要么继续离远点更远，要么靠近远点，但是不会大于当前距离。

那我们还可以看出 $x,y$ 轴之间没有影响，那我们可以随便吧数分成两部分，数量都是 $n$。然后分别处理。

那我们还是只看 $x$ 轴的那 $n$ 个数。

代码

#include
   
    #include
    
     using namespace std;int n, a[20001], u[20001], x[20001], y[20001];int l1, r1, zff[20001], l2, r2;int xsum, ysum;bool cmp(int x, int y) {   	return x < y;}void zf(int x) {   	if (x == 1) printf("+");		else printf("-");}int main() {   	scanf("%d", &n);	for (int i = 1; i <= 2 * n; i++) scanf("%d", &a[i]);		sort(a + 1, a + 2 * n + 1, cmp);		for (int i = 1; i <= n; i++) {   		scanf("%d", &u[i]);				if (u[i] & 1) {   //记录xy坐标正负性			if (u[i] / 2) x[i] = y[i] = -1;				else x[i] = y[i] = 1;		}		else if (u[i] / 2 == 1) {   			x[i] = -1;			y[i] = 1;		}		else {   			x[i] = 1;			y[i] = -1;		}				if (i > 1) {   //统计要多少个小的			if (x[i] == x[i - 1]) l1++;			if (y[i] == y[i - 1]) l2++;		}	}	r1 = l1 + 1;	r2 = l2 + 1;		zff[n] = x[n];//得出数的正负	zff[n + n] = y[n];	for (int i = n - 1; i >= 1; i--) {   		zff[i] = zff[i + 1] * -1;		zff[n + i] = zff[n + i + 1] * -1;	}		zf(zff[r1]);//先处理第一个数	printf("%d ", a[r1]);	r1++;	zf(zff[n + r2]);	printf("%d\n", a[n + r2]);	r2++;	for (int i = 2; i <= n; i++) {   		if (zff[r1 - 1] * x[i] < 0) {   //选大的			zf(zff[r1]);			printf("%d ", a[r1]);			r1++;		}		else {   //选小的			zf(zff[l1]);			printf("%d ", a[l1]);			l1--;		}		if (zff[n + r2 - 1] * y[i] < 0) {   //同理			zf(zff[n + r2]);			printf("%d\n", a[n + r2]);			r2++;		}		else {   			zf(zff[n + l2]);			printf("%d\n", a[n + l2]);			l2--;		}	}		return 0;}