题解 | #复数集合#

一次堆排序当然比很多次sort快很多 一次堆排序虽然和一次快排时间复杂度一样，但是优先队列的使用是整个堆排序流程的拆散、充分利用，做入堆、出堆这么多事情，其实整体只不过是一次堆排序，是一次建堆、输出序列的顺序打乱版本而已。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>

using namespace std;

class Complex{
public:
	int real;
	int imag;
	Complex(int a, int b):real(a),imag(b){}
	bool operator<(const Complex &c) const {
		if(real*real+imag*imag==c.real*c.real+c.imag*c.imag){
			return imag > c.imag;
		}else{
			return real*real+imag*imag < c.real*c.real+c.imag*c.imag;
		}
	}
};



int main(){
	int n;
	while(scanf("%d",&n) != EOF){
		priority_queue<Complex> q;
		while(n--){
			string s;
			cin >> s;
			if(s == "Pop"){
				if(q.empty()){
					printf("empty\n");
				}else{
					Complex current = q.top();
					q.pop();
					printf("%d+i%d\n", current.real, current.imag);
					printf("SIZE = %d\n", q.size());
				}
			}else{
				int a,b;
				scanf("%d+i%d", &a, &b);
				q.push(Complex(a,b));
				printf("SIZE = %d\n",q.size());
			}
		}
	}
	return 0;
}

//int main(){
//	int n;
//	while(scanf("%d",&n) != EOF){
//		vector<Complex> v;
//		while(n--){
//			string s;
//			cin >> s;
//			if(s == "Pop"){
//				if(v.empty()){
//					printf("empty\n");
//				}else{
//					Complex current = v[v.size()-1];
//					v.erase(v.end()-1);
//					printf("%d+i%d\n", current.real, current.imag);
//					printf("SIZE = %d\n", v.size());
//				}
//			}else{
//				int a,b;
//				scanf("%d+i%d", &a, &b);
//				v.push_back(Complex(a,b));
//				sort(v.begin(),v.end());
//				printf("SIZE = %d\n",v.size());
//			}
//		}
//	}
//	return 0;
//}