UVA 11039 Building designing

UVA_11039

    假设当前要放一个blue的floor，那么这个floor的size应当是越大越好的，因为这样做相比于选一个size较小的，至少不会使结果变得更糟。于是接下来的工作只要枚举最下面是放的blue的或者red的，然后向上依次选择颜色交替的、size尽量大的floor即可。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 500010
int N, a[MAXN];
bool cmp(int x, int y)
{
    return std::abs(x) < std::abs(y);
}
inline int getst(int x)
{
    return x > 0;
}
void input()
{
    scanf("%d", &N);
    for(int i = 0; i < N; i ++) scanf("%d", &a[i]);
    std::sort(a, a + N, cmp);
}
int deal(int st, int inf)
{
    int cnt = 0;
    for(int i = N - 1; i >= 0; i --)
        if(st != getst(a[i]) && std::abs(a[i]) < inf)
            ++ cnt, inf = std::abs(a[i]), st ^= 1;
    return cnt;
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t --)
    {
        input();
        printf("%d\n", std::max(deal(0, 1000000), deal(1, 1000000)));
    }
    return 0;
}