题目链接：http://acm.ocrosoft.com/problem.php?cid=1615&pid=13
题目描述：
给你一个长度为N的数组，一个长为K的滑动窗体从最左端移至最右端，你只能看到窗口中的K个数，每次窗体向右移动一位，如下表所示：
窗口位置 最小值 最大值
[ 1 3 -1 ] -3 5 3 6 7 -1 3
1 [ 3 -1 -3 ] 5 3 6 7 -3 3
1 3 [ -1 -3 5 ] 3 6 7 -3 5
1 3 -1 [ -3 5 3 ] 6 7 -3 5
1 3 -1 -3 [ 5 3 6 ] 7 3 6
1 3 -1 -3 5 [ 3 6 7 ] 3 7
你的任务是找出窗体在各个位置时的最大值和最小值。
输入
第一行：两个整数N和K
第二行：N个整数，表示数组的N个元素（<=2*10^9）。
输出
第一行为滑动窗口从左向右移动到每个位置时的最小值，每个数之间用一个空格分开。
第一行为滑动窗口从左向右移动到每个位置时的最大值，每个数之间用一个空格分开。
样例输入：
8 3
1 3 -1 -3 5 3 6 7
样例输出：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
思路：
建一个dp[i][j],i表示从i的位置开始扫描，j表示从i开始（i也包括）往后扫描（1<<j）个数
然后直接RMQ算法，输出的时候优化一下就行了。
这题本身其实是用单调队列写的，想看单调队列的写法可以直接去这个网址，注释不想打了，就是完完全全没有加另外其他任何东西的单调队列。
单调队列AC代码：https://paste.ubuntu.com/p/vXdJJGQqQs/
dp+rmq算法代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int dp[1000005][30];//动态规划 ，dp[i][j],j的意思是1<<j(扫描的个数)！！ j的意思是1<<j(扫描的个数)！！ j的意思是1<<j(扫描的个数)！！ 重要的事情说3遍！！！
int a[1000005];//用于存储数字
void st_max(int m)//初始化dp
{
for (int i = 1; i <= m; i++)
{
dp[i][0] = a[i];//j位置为0时，相当于1<<0=1,所以在范围为1的区间里的最值就是a[i]
}
for (int j = 1; (1 << j) <= m; j++)
{
for (int i = 1; i + (1 << j) - 1 <= m; i++)
{
dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
//这里不太好解释，就是比如i到i+(1<<j)-1个数分为2组，一组是i到 i+(1<<(j-1))-1，另一组是 i+(1<<(j-1))到i+(1<<j)-1，进行动态规划
}
}
}
int rmq_max(int l, int r)//取l到r区间里的最值
{
int k = 0;
while ((1 << (k + 1)) <= r - l + 1)k++;//找到某个k可以让2块长为（1<<k）的区间将l到r的区间完全覆盖
return max(dp[l][k], dp[r - (1 << k) + 1][k]);//取最值
}
void st_min(int m)//这个和上诉一猫一样
{
for (int i = 1; i <= m; i++)
{
dp[i][0] = a[i];
}
for (int j = 1; (1 << j) <= m; j++)
{
for (int i = 1; i + (1 << j) - 1 <= m; i++)
{
dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
}
}
int rmq_min(int l, int r)
{
int k = 0;
while ((1 << (k + 1)) <= r - l + 1)k++;
return min(dp[l][k], dp[r - (1 << (k)) + 1][k]);
}
int main()
{
int n;
scanf("%d", &n);
int k;
scanf("%d", &k);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
st_min(n);
//这里就是输出答案时的优化
//假如你已经有了某个区间的最值，并且这个区间起点不是最值，那么下个区间的最值只需要用新加进来的元素和原来的最值比对，否则重新RMQ跑一遍
int minn = rmq_min(1, 1 + k - 1);// 有了第一个区间的最值
printf("%d ", minn);
for (int i = 2; i <= n - k + 1; i++)
{
if (a[i - 1] == minn)//假如这个区间的最值就是第一个数，那算后一个区间就要RMQ重新跑一遍
{
printf("%d ",rmq_min(i, i + k - 1) );
minn = rmq_min(i, i + k - 1);//重新记录最值
}
else
{
minn = min(minn, a[i + k - 1]);// 新区间的最值只需要用新加进来的元素和原来的最值比对
printf("%d ", minn);
}
}
/*这里是TLE的输出代码，直接暴力RMQ会TLE
for (int i = 1; i <= n - k + 1; i++)
{
cout << rmq_min(i, i + k - 1) << " ";
}*/
cout << endl;
memset(dp, 0, sizeof(dp));
st_max(n);
//和上诉一毛一样
int maxx = rmq_max(1, 1 + k - 1);
printf("%d ", maxx);
for (int i = 2; i <= n - k + 1; i++)
{
if (a[i - 1] == maxx)
{
printf("%d ",rmq_max(i, i + k - 1) );
maxx = rmq_max(i, i + k - 1);
}
else
{
maxx = max(maxx, a[i + k - 1]);
printf("%d ", maxx);
}
}
/*
for (int i = 1; i <= n - k + 1; i++)
{
cout << rmq_max(i, i + k - 1) << " ";
}*/
return 0;
}
单调队列代码：
#include<iostream>
#include<deque>
#include<stdio.h>
using namespace std;
struct www
{
int zhi;
int pos;
}a[1000005];
int zeng1[1000005];
int jian1[1000005];
int lenzeng = 1;
int lenjian = 1;
int main()
{
int n, k;
cin >> n >> k;
deque<www>zeng;
deque<www>jian;
int num = 1;
for (int i = 1; i <= n; i++)
{
www x;
scanf("%d", &x.zhi);
x.pos = i;
if (num < k)
{
num++;
if (zeng.empty())
{
zeng.push_back(x);
}
else
{
while (zeng.back().zhi >= x.zhi)
{
zeng.pop_back();
if (zeng.empty())
{
break;
}
}
zeng.push_back(x);
}
if (jian.empty())
{
jian.push_back(x);
}
else
{
while (jian.back().zhi <= x.zhi)
{
jian.pop_back();
if (jian.empty())
{
break;
}
}
jian.push_back(x);
}
}
else
{
if (i - zeng.front().pos == k)
{
zeng.pop_front();
if (zeng.empty())
{
zeng.push_back(x);
}
else
{
while (zeng.back().zhi >= x.zhi)
{
zeng.pop_back();
if (zeng.empty())
{
break;
}
}
zeng.push_back(x);
}
zeng1[lenzeng++] = zeng.front().zhi;
}
else
{
while (zeng.back().zhi >= x.zhi)
{
zeng.pop_back();
if (zeng.empty())
{
break;
}
}
zeng.push_back(x);
zeng1[lenzeng++] = zeng.front().zhi;
}
if (i -jian.front().pos == k)
{
jian.pop_front();
if (jian.empty())
{
jian.push_back(x);
}
else
{
while (jian.back().zhi <= x.zhi)
{
jian.pop_back();
if (jian.empty())
{
break;
}
}
jian.push_back(x);
}
jian1[lenjian++] = jian.front().zhi;
}
else
{
while (jian.back().zhi <= x.zhi)
{
jian.pop_back();
if (jian.empty())
{
break;
}
}
jian.push_back(x);
jian1[lenjian++] = jian.front().zhi;
}
}
}
for (int i = 1; i < lenzeng; i++)
{
printf("%d ", zeng1[i]);
}
printf("\n");
for (int i = 1; i < lenjian; i++)
{
printf("%d ", jian1[i]);
}
return 0;
}
京公网安备 11010502036488号