UVa 11039 (排序+贪心) Building designing

白书上的例题比较难，认真理解样例代码有助于提高自己

后面的练习题相对简单，独立思考解决问题，增强信心

题意：n个绝对值各不相同的非0整数，选出尽量多的数排成序列，使得该序列正负交错且绝对值递增。

解法：先按绝对值从小到大排序，然后第一个数先入队，然后依次比较后面的数，如果和队尾的数符号相反则入队，直到所有的数遍历完为止

这里用了异或运算，因为这里面没有0，所谓符号相同的两个数异或值为正，不同符号的数异或值为负

//#define LOCAL
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

const int maxn = 500000 + 10;
int a[maxn];
bool cmp(int a, int b)
{
    return abs(a) < abs(b);
}

int main(void)
{
    #ifdef LOCAL
        freopen("11039in.txt", "r", stdin);
    #endif

    int T, n;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        sort(a, a+n, cmp);
        int q = 0, cnt = 1;
        for(int i = 1; i < n; ++i)
            if((a[i] ^ a[q]) < 0)
            {
                q = i;
                ++cnt;
            }
        printf("%d
", cnt);
    }
    return 0;
}