学步园

点击打开链接uva 11039

思路：贪心（排序+枚举）
分析：
1 题目要求按照题目给定的数据求能够建立最高几层的楼房
2 题目要求上层的大小要比下层小，并且两层之间的颜色要交替的出现。很明显，我们只要按照size进行排序，然后枚举即可。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 500010;
int n , Case;
struct floor{
    int color;
    int size;
    bool operator<(const floor &fl)const{
        return size > fl.size;
    }
};
floor f[MAXN];

int main(){
    scanf("%d" , &Case);
    while(Case--){
        scanf("%d" , &n);
        for(int i = 0 ; i < n ; i++){
           scanf("%d" , &f[i].color);
           f[i].size = abs(f[i].color);
        }
        sort(f , f+n);
        int ans , preSize , preColor;
        ans = 1;
        preSize = f[0].size;
        preColor = f[0].color;
        for(int i = 1 ; i < n ; i++){
           if(f[i].color > 0){
              if(preColor < 0){
                 ans++;
                 preColor = f[i].color;
              }
           }
           else{
              if(preColor > 0){
                 ans++;
                 preColor = f[i].color;
              }
           }
        }
        printf("%d\n" , ans);
    }
    return 0;
}