【POJ 1148】Utopia Divided
Utopia Divided
题目链接:POJ 1148
题目大意
在一个坐标系中,一个点一开始在原点,然后被要求每次走到一个规定的象限内。
你有一些互不相同的数,每次你可以选每选过的两个,正负性可以自己改,使得点的坐标加上这两个数。
所有数会刚好用完。
要你输出任意一种合法方案,如果没有方案就输出 0。
思路
这道题我们可以用贪心的思想来做。
我们考虑让
x
,
y
x,y
x,y 轴分开。
我们先以
x
x
x 轴为例子,
y
y
y 轴同理。
按假设现在是正的,你要改成负的(或者负的改成正的),那你就要加或减一个比当前坐标绝对值大的数。
那选数就是选比上一次选还要大的数。
那如果跟原来一样,那你可能有两个选择。要么继续离远点更远,要么靠近远点,但是不会大于当前距离。
那你为了到时还可以改正负,你肯定是让离原点近一点好。
那我们就一定是选比上一次选还要小的数。
那我们还可以看出 x , y x,y x,y 轴之间没有影响,那我们可以随便吧数分成两部分,数量都是 n n n。然后分别处理。
那我们还是只看
x
x
x 轴的那
n
n
n 个数。
那我们就通过看象限的变化,以及当时的位置,就可以贪心出选大的还是小的,正的还是负的了。
代码
#include<cstdio>
#include<algorithm>
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;
}