P1631序列合并

第二道独立ac的绿题。

using i64 = long long;
template<typename T>
class smallest_heap {
private:
	T heap[100005];
	int len;
public:
	smallest_heap();
	void push(T const&);
	void pop();
	T top();
	int size();
	bool empty();
};
template<typename T>
smallest_heap<T>::smallest_heap() {
	len = 0;
	memset(heap, 0, sizeof(heap));
}
template<typename T>
void smallest_heap<T>::push(T const& n) {
	heap[++len] = n;
	int son = len, father = son / 2;
	while (heap[son] > heap[father]&&father>=1) {
		std::swap(heap[son], heap[father]);
		son = father, father = son / 2;
	}
}
template<typename T>
void smallest_heap<T>::pop() {
	std::swap(heap[1], heap[len]);
	heap[len--] = 0;
	int son = 2, father = 1;
	while (son <= len) {
		if (son<len && heap[son]<heap[son + 1])son++;
		if (heap[son] > heap[father]) {
			std::swap(heap[son], heap[father]);
			father = son, son = father * 2;
		}
		else break;
	}
}

template<typename T>
T smallest_heap<T>::top() {
	return heap[1];
}
template<typename T>
int smallest_heap<T>::size() {
	return len;
}

template<typename T>
bool smallest_heap<T>::empty() {
	return len;
}
smallest_heap<i64>h;
int main() {
	int n;
	std::cin >> n;
	std::vector<i64>a(n+1), b(n+1);
	for (int i = 0; i < n; i++)std::cin >> a[i];
	for (int i = 0; i < n; i++)std::cin >> b[i];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			i64 x = a[i] + b[j];
			if (h.size() < n)h.push(x);
			else {
				if (h.top() > x) {
					h.pop();
					h.push(x);
				}
				else break;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		a[i] = h.top();
		h.pop();
	}
	for (int i = n - 1; i >= 0; i--)std::cout << a[i] << ' ';
	return 0;
}

写一个大顶堆（大顶堆和小顶堆的模版我都发过，可以去看看我前面的文章），然后枚举a[i]+b[j]，当a[i]+b[j]>h.top()的时候说明a[i]+a[j+1]……都大于h.top()然后break，思路很简单，最后依次取出最大的，然后从最后一个，及最小的开始打印。