2014年8月13日 星期三

UVA 11039

greedy
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int an[500005];
int __abs(int x){
    if(x > 0) return x;
    return -x;
}
struct cp{
    bool operator()(int a, int b){
        return __abs(a) < __abs(b);
    }
}CP;
int main(){
    int T;scanf("%d", &T);
    while(T-->0){
        int n;scanf("%d", &n);
        for(int lx = 0;lx < n;lx++)
            scanf("%d", an+lx);
        sort(an, an + n, CP);
        int neg = 0, pos = 0;
//        int neg_ind = -1, pos_ind = -1;
        for(int lx =0;lx < n;lx++){
            if(an[lx] < 0) pos = max(pos, neg+1);
            if(an[lx] > 0) neg = max(neg, pos+1);
        }
        printf("%d\n", max(neg, pos));
    }
    return 0;
}

沒有留言:

張貼留言