POJ2823 Sliding Window(单调队列,线段树,set,deque)
Description
Input
Output
Sample Input8 3 1 3 -1 -3 5 3 6 7 Sample Output-1 -3 -3 -3 3 3 3 3 5 5 6 7 思路这是著名的滑动窗口问题,就是单调队列的基本问题。。这道题主要说一下单调队列解法
一般来说, 代码单调队列: #include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <sstream>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt << 1
#define rson m + 1,r,rt << 1 | 1
#define rson m + 1,rt << 1 | 1
#define inf 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int> pir;
const int N = 1e6 + 10;
deque<pir> q1; //维护最大值
deque<pir> q2; //维护最小值
int x,MIN[N],MAX[N];
int main()
{
//freopen("in.txt","r",stdin);
int n,k;
scanf("%d%d",&n,&k);
for (int i = 1; i <= n; i++)
{
scanf("%d",&x);
while (!q1.empty() && q1.back().first >= x) //队列递增
q1.pop_back();
q1.push_back(make_pair(x,i));
if (i >= k)
{
while (!q1.empty() && q1.front().second <= i - k) //>的时候出去
q1.pop_front();
MIN[i] = q1.front().first;
}
while (!q2.empty() && q2.back().first <= x) //队列递减
q2.pop_back();
q2.push_back(make_pair(x,i));
if (i >= k)
{
while (!q2.empty() && q2.front().second <= i - k)
q2.pop_front();
MAX[i] = q2.front().first;
}
}
for (int i = k; i <= n; i++)
printf("%d ",MIN[i]);
puts("");
for (int i = k; i <= n; i++)
printf("%d ",MAX[i]);
puts("");
return 0;
}
set做法(poj过不了,scu可过) #include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <sstream>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;
#define mem(a,rt << 1 | 1
#define inf 0x3f3f3f3f
typedef long long ll;
const int N = 1e6 + 10;
multiset<int> s;
int a[N],ans1[N],ans2[N];
int main()
{
// freopen("in.txt",k;
while (~scanf("%d%d",&k))
{
s.clear();
for (int i = 1; i <= n; i++)
{
scanf("%d",&a[i]);
if (i <= k)
s.insert(a[i]);
}
for (int i = 1; i <= n - k + 1; i++)
{
int j = i + k - 1;
ans1[i] = *s.begin();
ans2[i] = *s.rbegin();
s.erase(s.find(a[i]));
s.insert(a[j + 1]);
}
for (int i = 1; i <= n - k + 1; i++)
{
printf("%d ",ans1[i]);
}
printf("n");
for (int i = 1; i <= n - k + 1; i++)
{
printf("%d ",ans2[i]);
}
printf("n");
}
return 0;
}
线段树: #include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <sstream>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;
#define mem(a,rt << 1 | 1
#define inf 0x3f3f3f3f
typedef long long ll;
const int N = 1e6 + 10;
int ans1[N],ans2[N];
int MAX[N << 2],MIN[N << 2];
void pushup(int rt)
{
MAX[rt] = max(MAX[rt << 1],MAX[rt << 1 | 1]);
MIN[rt] = min(MIN[rt << 1],MIN[rt << 1 | 1]);
}
void build(int l,int r,int rt)
{
if (l == r)
{
scanf("%d",&MAX[rt]);
MIN[rt] = MAX[rt];
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushup(rt);
}
void update(int p,int add,int l,int rt)
{
if (l == r)
{
MAX[rt] = add;
MIN[rt] = add;
return;
}
int m = (l + r) >> 1;
if (p <= m)
update(p,add,lson);
else
update(p,rson);
pushup(rt);
}
int query_max(int L,int R,int rt)
{
if (L <= l && r <= R)
return MAX[rt];
int m = (l + r) >> 1;
int ans = -inf;
if (L <= m)
ans = max(ans,query_max(L,R,lson));
if (R > m)
ans = max(ans,rson));
return ans;
}
int query_min(int L,int rt)
{
if (L <= l && r <= R)
return MIN[rt];
int m = (l + r) >> 1;
int ans = inf;
if (L <= m)
ans = min(ans,query_min(L,lson));
if (R > m)
ans = min(ans,rson));
return ans;
}
int main()
{
//freopen("in.txt",&k))
{
build(1,n,1);
for (int i = 1; i <= n - k + 1; i++)
{
int j = i + k - 1;
ans2[i] = query_max(i,j,1,1);
ans1[i] = query_min(i,1);
}
for (int i = 1; i <= n - k + 1; i++)
printf("%d ",ans1[i]);
printf("n");
for (int i = 1; i <= n - k + 1; i++)
printf("%d ",ans2[i]);
printf("n");
}
return 0;
} (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- windows – Win32_LogonSessions返回旧会话
- Odata压缩 – 是否有任何支持? (WinRT的WCF数据服务5.0)
- 如何设置服务器支持.shtml类型文件
- azure – MSBuild在构建时失败,正在寻找旧版本的Microsoft.
- windows – 自定义MSI安装程序
- Windows关机对话框
- Windows Server 2008 R2 + IIS 环境部署Asp.Net Core App
- 在哪里可以找到Microsoft docx格式的架构(.xsd文件)
- winapi – 当你可以使用RET时,为什么在Win32下需要ExitProc
- windows – 带有通用应用程序的系统托盘/任务栏图标/通知图