思路:贪心(排序+枚举)
分析:
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; }
时间: 2024-10-26 02:12:38