【题解】UVa 11039【Building designing】

分析

这题其实很水的,模拟即可,咱们贪心的求解,先按绝对值排个序,当值相等时,把符号为负的排在前面。然后一遍循环扫过去记录答案就好了。

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using std::sort;using std::abs;
const int MAXN = 500000 + 6;
int A[MAXN];
inline bool cmp(int a,int b){return abs(a) < abs(b) || (abs(a) == abs(b) && a < b);}

int main(){
    int T;scanf("%d",&T);
    while(T--){
        int n;scanf("%d",&n);
        memset(A,0,sizeof(A));
        for(int i = 0;i < n;i++) scanf("%d",&A[i]);
        sort(A,A + n,cmp);
        int ans = 1;
        for(int i = 1;i < n;i++){
            if(A[i - 1] > 0 && A[i] < 0){ans++;continue;}
            if(A[i - 1] < 0 && A[i] > 0){ans++;continue;}
        }
        printf("%d\n",ans);
    }

    return 0;
}