想问这个代码错哪了
查看原帖
想问这个代码错哪了
1159937
520689892yhw楼主2024/1/6 11:21
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();
	void pop_back();
	T top();
	T back();
	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>
T smallest_heap<T>::back() {
	return heap[len];
}
template<typename T>
void smallest_heap<T>::pop_back() {
	heap[len--] = 0;
}
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.back() > x) {
					h.pop_back();
					h.push(x);
				}
				else break;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		std::cout << h.top()<<' ';
		h.pop();
	}
	return 0;
}
2024/1/6 11:21
加载中...