复兴提高DAY01堆及其应用
2025-07-02 21:54:04
发布于：上海
16阅读
0回复
0点赞
T1【堆及其应用一】大根堆
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
int heap[maxn], heap_size;
void put(int d) {
int son, pa;
heap[++heap_size] = d;//新增一个结点，值为d
son = heap_size;
while (son > 1) { //向上调整，使其满足大根堆的性质
pa = son >> 1; //找到父节点
if (heap[son] <= heap[pa]) break; //如果父节点的值大于等于儿子结点，调整完毕
swap(heap[son], heap[pa]); //向上调整
son = pa;
}
}
//返回堆顶的值，并删除堆顶
int get() {
int pa, son, res;
res = heap[1]; //存储堆顶的值
heap[1] = heap[heap_size--]; //用最后一个元素覆盖堆顶，并把堆元素个数减一
pa = 1;
//向下调整
while (pa * 2 <= heap_size) {
son = pa * 2;
if (son < heap_size && heap[son + 1] > heap[son]) son++;//找到存在的儿子中最大的一个
if (heap[pa] >= heap[son]) break; //调整完毕
swap(heap[pa], heap[son]);//向下调整
pa = son;
}
return res;//返回堆顶的值
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
put(x);
}
for (int i = 1; i <= n; i++) cout << heap[i] << " ";
return 0;
}
T2【堆及其应用一】排序1
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
int heap[maxn], heap_size;
void put(int d) {
int son, pa;
heap[++heap_size] = d;//新增一个结点，值为d
son = heap_size;
while (son > 1) { //向上调整，使其满足大根堆的性质
pa = son >> 1; //找到父节点
if (heap[son] <= heap[pa]) break; //如果父节点的值大于等于儿子结点，调整完毕
swap(heap[son], heap[pa]); //向上调整
son = pa;
}
}
//返回堆顶的值，并删除堆顶
int get() {
int pa, son, res;
res = heap[1]; //存储堆顶的值
heap[1] = heap[heap_size--]; //用最后一个元素覆盖堆顶，并把堆元素个数减一
pa = 1;
//向下调整
while (pa * 2 <= heap_size) {
son = pa * 2;
if (son < heap_size && heap[son + 1] > heap[son]) son++;//找到存在的儿子中最大的一个
if (heap[pa] >= heap[son]) break; //调整完毕
swap(heap[pa], heap[son]);//向下调整
pa = son;
}
return res;//返回堆顶的值
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
put(x);
}
while (heap_size) {
cout << get() << " ";
}
return 0;
}
T3【堆及其应用一】排序2
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
int heap[maxn], heap_size;
void put(int d) {
int son, pa;
heap[++heap_size] = d;//新增一个结点，值为d
son = heap_size;
while (son > 1) { //向上调整，使其满足小根堆的性质
pa = son >> 1; //找到父节点
if (heap[son] >= heap[pa]) break; //如果父节点的值小于等于儿子结点，调整完毕
swap(heap[son], heap[pa]); //向上调整
son = pa;
}
}
//返回堆顶的值，并删除堆顶
int get() {
int pa, son, res;
res = heap[1]; //存储堆顶的值
heap[1] = heap[heap_size--]; //用最后一个元素覆盖堆顶，并把堆元素个数减一
pa = 1;
//向下调整
while (pa * 2 <= heap_size) {
son = pa * 2;
if (son < heap_size && heap[son + 1] < heap[son]) son++;//找到存在的儿子中最小的一个
if (heap[pa] <= heap[son]) break; //调整完毕
swap(heap[pa], heap[son]);//向下调整
pa = son;
}
return res;//返回堆顶的值
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
put(x);
}
while (heap_size) {
cout << get() << " ";
}
return 0;
}
T4【堆及其应用一】小根堆
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
int heap[maxn], heap_size;
void put(int d) {
int son, pa;
heap[++heap_size] = d;//新增一个结点，值为d
son = heap_size;
while (son > 1) { //向上调整，使其满足小根堆的性质
pa = son >> 1; //找到父节点
if (heap[son] >= heap[pa]) break; //如果父节点的值小于等于儿子结点，调整完毕
swap(heap[son], heap[pa]); //向上调整
son = pa;
}
}
//返回堆顶的值，并删除堆顶
int get() {
int pa, son, res;
res = heap[1]; //存储堆顶的值
heap[1] = heap[heap_size--]; //用最后一个元素覆盖堆顶，并把堆元素个数减一
pa = 1;
//向下调整
while (pa * 2 <= heap_size) {
son = pa * 2;
if (son < heap_size && heap[son + 1] < heap[son]) son++;//找到存在的儿子中最小的一个
if (heap[pa] <= heap[son]) break; //调整完毕
swap(heap[pa], heap[son]);//向下调整
pa = son;
}
return res;//返回堆顶的值
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
put(x);
}
for (int i = 1; i <= n; i++) cout << heap[i] << " ";
return 0;
}
T5【堆及其应用一】黑匣子
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 9;
int a[maxn], u[maxn];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> u[i];
priority_queue<int> q1;
priority_queue<int, vector<int>, greater<int> >q2;
int k = 1;
for (int i = 1, j = 1; i <= n; i++) {
if (q1.size()&&a[i] > q1.top()) q2.push(a[i]);
else q1.push(a[i]);
while (j<=m&&u[j] == i) {
while (q1.size() < k) {
q1.push(q2.top());
q2.pop();
}
while (q1.size() > k) {
q2.push(q1.top());
q1.pop();
}
cout << q1.top() << '\n';
k++;
j++;
}
}
return 0;
}
T6【堆及其应用二】合并果子
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 9;
int heap[maxn], heap_size;
void put(int d) {
int son, pa;
heap[++heap_size] = d;//新增一个结点，值为d
son = heap_size;
while (son > 1) { //向上调整，使其满足小根堆的性质
pa = son >> 1; //找到父节点
if (heap[son] >= heap[pa]) break; //如果父节点的值小于等于儿子结点，调整完毕
swap(heap[son], heap[pa]); //向上调整
son = pa;
}
}
//返回堆顶的值，并删除堆顶
int get() {
int pa, son, res;
res = heap[1]; //存储堆顶的值
heap[1] = heap[heap_size--]; //用最后一个元素覆盖堆顶，并把堆元素个数减一
pa = 1;
//向下调整
while (pa * 2 <= heap_size) {
son = pa * 2;
if (son < heap_size && heap[son + 1] < heap[son]) son++;//找到存在的儿子中最小的一个
if (heap[pa] <= heap[son]) break; //调整完毕
swap(heap[pa], heap[son]);//向下调整
pa = son;
}
return res;//返回堆顶的值
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
put(a);
}
int ans = 0;
while (heap_size > 1) {
int x = get(), y = get();
ans += x + y;
put(x + y);
}
cout << ans;
return 0;
}
T7【堆及其应用二】超市
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 9;
struct node {
int p, d;
}a[maxn];
bool cmp(node A, node B) {
return A.d < B.d;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].p >> a[i].d;
}
sort(a + 1, a + n + 1, cmp);
priority_queue<int, vector<int>, greater<int> >q;
for (int i = 1; i <= n; i++) {
if (a[i].d == q.size()) {
if (a[i].p > q.top()) {
q.pop();
q.push(a[i].p);
}
}
else {
q.push(a[i].p);
}
}
long long ans = 0;
while (q.size()) {
ans += q.top();
q.pop();
}
cout << ans;
return 0;
}
T8【堆及其应用二】调整后的堆
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 9;
int heap[maxn], heap_size;
void put(int d) {
int son, pa;
heap[++heap_size] = d;//新增一个结点，值为d
son = heap_size;
while (son > 1) { //向上调整，使其满足小根堆的性质
pa = son >> 1; //找到父节点
if (heap[son] >= heap[pa]) break; //如果父节点的值小于等于儿子结点，调整完毕
swap(heap[son], heap[pa]); //向上调整
son = pa;
}
}
//返回堆顶的值，并删除堆顶
int get() {
int pa, son, res;
res = heap[1]; //存储堆顶的值
heap[1] = heap[heap_size--]; //用最后一个元素覆盖堆顶，并把堆元素个数减一
pa = 1;
//向下调整
while (pa * 2 <= heap_size) {
son = pa * 2;
if (son < heap_size && heap[son + 1] < heap[son]) son++;//找到存在的儿子中最小的一个
if (heap[pa] <= heap[son]) break; //调整完毕
swap(heap[pa], heap[son]);//向下调整
pa = son;
}
return res;//返回堆顶的值
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
put(a);
}
while (heap_size) {
get();
for (int i = 1; i <= heap_size; i++) cout << heap[i] << " ";
cout << '\n';
}
return 0;
}
T9【堆及其应用二】动态最小值
#include<bits/stdc++.h>
using namespace std;
int main() {
int m;
cin >> m;
priority_queue<int, vector<int>,greater<int> > q;
while (m--) {
int opt;
cin >> opt;
if (opt == 1) {
int x;
cin >> x;
q.push(x);
cout << q.top() << '\n';
}
else {
if (q.size() == 0) cout << "impossible" << '\n';
else {
q.pop();
if (q.size() == 0)cout << "impossible" << '\n';
else cout << q.top() << '\n';
}
}
}
return 0;
}
T10【堆及其应用二】动态最大值
#include<bits/stdc++.h>
using namespace std;
int main() {
int m;
cin >> m;
priority_queue<int> q;
while (m--) {
int opt;
cin >> opt;
if (opt == 1) {
int x;
cin >> x;
q.push(x);
cout << q.top() << '\n';
}
else {
if (q.size() == 0) cout << "impossible" << '\n';
else {
q.pop();
if (q.size() == 0)cout << "impossible" << '\n';
else cout << q.top() << '\n';
}
}
}
return 0;
}
T11【堆及其应用二】第k小的数
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, m, k;
cin >> n >> m >> k;
priority_queue<int> q1;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
if (q1.size() < k) q1.push(a);
else {
if (q1.top() > a) {
q1.pop();
q1.push(a);
}
}
}
while (m--) {
int opt;
cin >> opt;
if (opt == 1) {
int a;
cin >> a;
if (q1.size() < k) q1.push(a);
else {
if (q1.top() > a) {
q1.pop();
q1.push(a);
}
}
}
else {
if (q1.size() >= k)cout << q1.top() << '\n';
else cout << "-1" << '\n';
}
}
return 0;
}
T12【堆及其应用二】小码君和士兵
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
struct node {
int v, s;
}a[maxn];
bool cmp(node A, node B) {
return A.s > B.s;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i].v >> a[i].s;
sort(a + 1, a + 1 + n, cmp);
long long sum = 0, ans = 0;
priority_queue<int, vector<int>, greater<int> > q;
for (int i = 1; i <= n; i++) {
while (q.size() >= a[i].s) {
sum -= q.top();
q.pop();
}
q.push(a[i].v);
sum += a[i].v;
ans = max(ans, sum);
}
cout << ans;
return 0;
}
这里空空如也
有帮助，赞一个