单调队列
单调队列这个东东之前学过一遍了~
但似乎忘得一干二净惹，或者当时就妹学会
NC50528 滑动窗口
模板（找最小的数）
l = 0;//左闭右开的区间
r = 1;
p[0] = 1;//数组p存的原数组的下标
if(k == 1) printf("%d ", ar[1]);//k是区间长度
for(int i = 2; i <= n; ++i)
{
if(i - p[l] >= k && (l < r)) l++;//判断队头有没有出窗口
while(r > l && ar[p[r - 1]] >= ar[i]) r--;//在保证队列里有元素的情况下，判断队列里的数是否有资格在队列里
p[r++] = i;
if(i >= k) printf("%d ", ar[p[l]]);//输出队头即可
}
//对于变量l，r具体的含义啊，老是不太明白，感觉自己明白了，但是说不明白。 按照这个套路记吧
1.初始化
l = 0;
r = 1;
p[0] = 1;2.循环里的4个步骤
（1）.判断队头头有没有出窗口
（2）.判断新来的元素是否会导致队列内元素的出队
（3）.新元素入队
（4）.是否符合输出条件，输出队头
完整AC代码：
#include <bits/stdc++.h>
using namespace std;
int n, k;
int ar[1000050];
int p[1000050];
int l, r;//左闭右开
int main()
{
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i) scanf("%d", &ar[i]);
l = 0;
r = 1;
p[0] = 1;
if(k == 1) printf("%d ", ar[1]);
for(int i = 2; i <= n; ++i)
{
if(i - p[l] >= k && (l < r)) l++;
while(r > l && ar[p[r - 1]] >= ar[i]) r--;
p[r++] = i;
if(i >= k) printf("%d ", ar[p[l]]);
}
putchar('\n');
l = 0;
r = 1;
p[0] = 1;
if(k == 1) printf("%d ", ar[1]);
for(int i = 2; i <= n; ++i)
{
if(i - p[l] >= k && (l < r)) l++;
while(r > l && ar[p[r - 1]] <= ar[i]) r--;
p[r++] = i;
if(i >= k) printf("%d ", ar[p[l]]);
}
putchar('\n');
return 0;
}
堆（优先队列） priority_queue
这个英文单词是真记不柱，太特喵的难记惹
堆的题很有可能与贪心有联系
普通的priority_queue都是大根堆
它是一棵完全二叉数
然后根是所有元素中最大的元素，每个节点都大于它的子节点，小于它的父节点（好像是废话），然后队列的队首就是根节点，之后两个元素是根节点的左右儿子，在之后就这样循环下去~
插入（push）原理：是先放在队列最后面然后不断向上访问它的父节点判断大小关系，是否需要和父节点交换
删除（pop）原理：删除的是根节点，即队首，原理是把最后一个节点放到跟节点然后与它两个儿子中大的那个比较，看是否需要换，循环下去
知道了这些后我们其实就可以用数组模拟出来这个东东了
然后大根堆和小根堆，就那么写就行了不用管里面那个vector是个什么东西
priority_queue<int, vector<int>, greater<int> > q1;//小根堆 priority_queue<int, vector<int>, less<int> > q2;//大根堆
还有就是因为普通的堆是大根堆，我们要用小根堆是可以向上面那么写，也可以不用，就用大根堆，然后push的时候push这个数的相反数就可以了，取top（）的时候记得再取回来即可
有个图片（小根堆）
NC16663 合并果子
分析：
其实没什么好分析的，毕竟模板题嘛
就是每次取最小的两个数记起来后再push回去，进行n-1次后就剩一个数了，把最后剩的那个数输出出来即可。
AC代码：
1.用优先队列写的
#include <bits/stdc++.h>
using namespace std;
priority_queue<int> q;
int n, x;
int a, b;
int ans;
int main()
{
cin >> n;
for(int i = 1; i <= n; ++i)
{
cin >> x;
q.push(-x);
}
for(int i = 1; i < n; ++i)
{
a = -q.top();
q.pop();
b = -q.top();
q.pop();
ans += a + b;
q.push(-a-b);
}
cout << ans << '\n';
return 0;
}
2.数组模拟写的
需要我们自己写出push，pop，top这三个函数即可
#include <bits/stdc++.h>
using namespace std;
int ar[10050];
int tot;
int ans, x, n, a, b;
void push(int x)
{
ar[++tot] = x;
int i = tot;
int j = i / 2;
while(ar[i] < ar[j])
{
swap(ar[i], ar[j]);
i = j;
j = i / 2;
}
}
int top()
{
return ar[1];
}
void pop()
{
ar[1] = ar[tot--];
int i = 1;
int j = 2 * i;
if(j + 1 <= tot && ar[j + 1] < ar[j]) ++j;
while(j <= tot && ar[i] > ar[j])
{
swap(ar[j], ar[i]);
i = j;
j = 2 * i;
if(j + 1 <= tot && ar[j + 1] < ar[j]) ++j;
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; ++i)
{
cin >> x;
push(x);
}
for(int i = 1; i < n; ++i)
{
a = top();
pop();
b = top();
pop();
ans += a + b;
push(a + b);
}
cout << ans << '\n';
return 0;
}
对顶堆
一个大根堆一个小根堆，顶起来，比较形象哈，用语言不好描述，哈哈~
NC50940 Running Median
题意：
找中位数，找数组前1，3，5，7...个元素中的中位数
先输入一个t，代表有t组样例
然后每组第一行输入一个n和m，代表这是第n组样例，有m个数
接下来输入这m个数，一行输10个数，这个不用管输的时候会自己打回车，哈哈~
输出是这样子的，对于每对样例先输出，它的样例编号和应该输出几个数
之后输出中位数，要求每10个数换一次行
分析：
使用秘技·对顶堆
用两个堆，一个大根堆，一个小根堆，然后大数放小根堆，小数放大根堆，保证这两个堆中元素数相差不超过1，每次输出数多的那个堆顶即可。
我认为规定q2（大根堆，放小数的）中元素数大于等于q1中，然后每次输就只输q2.top（）即可
具体写法如下：
1.读进来数字后，先把第一个放在q2中
2.从2~m循环，每个数判断它与q2堆顶的关系，如果大于说明这是个大数，需要放q1，否则放q2，然后需要判断这两个堆的元素个数，之前说了规定q2中元素多，如果q1中元素多，需要把q1的顶放到q2中，并且在q1中pop，之后判断这是不是奇数，是则取q2堆顶放入ans数组中，为什么要用这个数组呢？因为要每输出10个数换一次行，这个问题单独考虑
3.输出，注意每10个数换行
4.最后判断输出的数是不是10的倍数，不是的话需要再换个行，要不然相邻两个样例连在一块了。
AC代码：
#include <bits/stdc++.h>
using namespace std;
priority_queue<int, vector<int>, greater<int> > q1;//小根堆
priority_queue<int, vector<int>, less<int> > q2;//大根堆
int n, m, t;
int x, x1, x2;
int ar[10050];
int main()
{
scanf("%d", &t);
while(t--)
{
while(!q1.empty()) q1.pop();
while(!q2.empty()) q2.pop();
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++i) scanf("%d", &ar[i]);
printf("%d %d\n", n, (m + 1) / 2);
if(m == 1)
{
printf("%d\n", ar[1]);
continue;
}
q2.push(ar[1]);
int sum = 0;
ar[++sum] = ar[1];
for(int i = 2; i <= m; ++i)
{
if(ar[i] > q2.top()) q1.push(ar[i]);
else q2.push(ar[i]);
while(q1.size() > q2.size())
{
q2.push(q1.top());
q1.pop();
}
while(q2.size() > q1.size() + 1)
{
q1.push(q2.top());
q2.pop();
}
if(i & 1) ar[++sum] = q2.top();
}
for(int i = 1; i <= sum; ++i)
{
printf("%d ", ar[i]);
if(i % 10 == 0) printf("\n");
}
if((m+1)/2 %10 != 0) putchar('\n');
}
return 0;
}
京公网安备 11010502036488号