Building designing

11039.cpp

#include <vector>
#include <algorithm> // for sort()
#include <cstdlib> // for abs()
#include <iostream>
using namespace std;

inline int back_or_0(const vector<int> &v) {
	return (v.size()>0)? v.back(): 0;
}
inline int pop_out(vector<int> &v) {
	int x=v.back();
	v.pop_back();
	return x;
}

int pop_next_smaller(vector<int> &v,int x) {
	while (v.size()>0 && v.back()>=x) v.pop_back();
	if (v.size()>0) return pop_out(v);
	return 0;
}

int max_floor(vector<int> &a,vector<int> &b) {
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	
	int num=0,pre=1<<30;
	// the vector has the greatest number goes first.
	switch (back_or_0(a)>back_or_0(b)) {
		while (true) {
		case true:
			pre=pop_next_smaller(a,pre);
			if (pre==0) return num;
			num++;
		case false:
			pre=pop_next_smaller(b,pre);
			if (pre==0) return num;
			num++;
		}
	}
}

int main() {
	int k;
	cin>>k;
	while (k--) {
		int n,x;
		vector<int> a,b;
		cin>>n;
		while (n--) {
			cin>>x;
			(x>0? a:b).push_back(abs(x));
		}
		cout<<max_floor(a,b)<<endl;
	}
	return 0;
}