第二道独立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,思路很简单,最后依次取出最大的,然后从最后一个,及最小的开始打印。