优先队列想法
求每个位置的前m个中的最小值
用一个双端的优先队列,升序
在维护时,要保证队首的位置在当前位置的前m个里
#include <bits/stdc++.h>
const int maxn = 2000050;
using namespace std;
typedef long long ll;
struct note
{
int val; //数值
int pos; //位置
} que[maxn];
int head, tail; //队列的头和尾
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
printf("%d
", que[head].val);
int x;
scanf("%d", &x);
while (head < tail && que[head].pos + m <= i) //删除头超出范围的
head++;
while (head < tail && que[tail - 1].val >= x) //保证队列是升序的
tail--;
que[tail].pos = i;
que[tail++].val = x;
}
// getchar();
// getchar();
return 0;
}
RMQ想法
如果不做出什么优化的话有两个点是会空间超限的
对于位置 i
i<=m 时 求的就是 区间 [1, i-1] 的最小值, ------>> 可以直接累积最小值就可以了
i>m时,求的是一段固定长度为 m 的 区间 [i-m, i-1] 的最小值 ------>> 用滚动数组 优化一下RMQ的
#include <bits/stdc++.h>
const int maxn = 2000050;
using namespace std;
typedef long long ll;
int dp[maxn][2]; //滚动数组
int n, m, pow2;
void init_rmq()
{
for (int j = 1; (1 << j) <= m; j++)
{
for (int i = 1; i + (1 << j) - 1 <= n; i++)
{
dp[i][j % 2] = min(dp[i][!(j % 2)], dp[i + (1 << (j - 1))][!(j % 2)]);
}
pow2 = j; //记录
}
}
int main()
{
scanf("%d%d", &n, &m);
printf("0
");
int minn = 3e8;
for (int i = 1; i <= n; i++)
{
scanf("%d", &dp[i][0]);
if (i <= m) // i<=m 的情况
{
if (i > 1)
printf("%d
", minn);
minn = min(dp[i][0], minn);
}
}
if (m == n)
return 0; //m == n 没必要继续求了
init_rmq();
for (int i = m + 1; i <= n; i++)
{
int l = i - m, r = i - 1;
printf("%d
", min(dp[l][pow2 % 2], dp[r - (1 << pow2) + 1][pow2 % 2])); //区间的长度是固定
}
// getchar();
// getchar();
return 0;
}
还是喜欢单调队列