Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

单调队列

Posted by hntby at 2018-12-15 11:09:57 on Problem 2823

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define M 1000000
using namespace std;
int n,m,a[M+1];

struct node{int pos,val;}q[M+1];

void getmin()
{
	int head=0,tail=-1;
	for (register int i=0;i<m-1;i++)
	{
		while (head<=tail&&q[tail].val>a[i]) tail--;
		q[++tail].val=a[i],q[tail].pos=i;
	}
	for (register int i=m-1;i<n;i++)
	{
		while (head<=tail&&i-q[head].pos>=m) head++;
		while (head<=tail&&q[tail].val>a[i]) tail--;
		q[++tail].val=a[i],q[tail].pos=i;
		printf("%d ",q[head].val);
	}
	printf("\n");
}

void getmax()
{
	int head=0,tail=-1;
	for (register int i=0;i<m-1;i++)
	{
		while (head<=tail&&q[tail].val<a[i]) tail--;
		q[++tail].val=a[i],q[tail].pos=i;
	}
	for (register int i=m-1;i<n;i++)
	{
		while (head<=tail&&i-q[head].pos>=m) head++;
		while (head<=tail&&q[tail].val<a[i]) tail--;
		q[++tail].val=a[i],q[tail].pos=i;
		printf("%d ",q[head].val);
	}
	printf("\n");
}

int main()
{
	scanf("%d%d",&n,&m);
	for (register int i=0;i<n;i++) scanf("%d",&a[i]);
	getmin(),getmax();
	return 0;
}

Followed by:

Re:单调队列 (1263) 0_2 2018-12-15 11:10:55
Re:单调队列 (1263) 0_3 2018-12-15 11:11:13
Re:单调队列 (1263) 0_4 2018-12-15 11:11:37
Re:单调队列 (1263) 0_5 2018-12-15 11:12:35
Re:单调队列 (1263) 0_6 2018-12-15 11:14:43
Re:单调队列 (1263) 0_7 2018-12-15 11:16:49
Re:单调队列 (1263) 0_8 2018-12-15 16:52:03
Re:单调队列 (1263) 0_9 2018-12-15 16:52:51

Post your reply here:

User ID:
Password:
Title:

Content:

> #include <iostream>
> #include <cstdio>
> #include <cstdlib>
> #include <cstring>
> #include <string>
> #include <algorithm>
> #include <cmath>
> #define M 1000000
> using namespace std;
> int n,m,a[M+1];
> 
> struct node{int pos,val;}q[M+1];
> 
> void getmin()
> {
> 	int head=0,tail=-1;
> 	for (register int i=0;i<m-1;i++)
> 	{
> 		while (head<=tail&&q[tail].val>a[i]) tail--;
> 		q[++tail].val=a[i],q[tail].pos=i;
> 	}
> 	for (register int i=m-1;i<n;i++)
> 	{
> 		while (head<=tail&&i-q[head].pos>=m) head++;
> 		while (head<=tail&&q[tail].val>a[i]) tail--;
> 		q[++tail].val=a[i],q[tail].pos=i;
> 		printf("%d ",q[head].val);
> 	}
> 	printf("\n");
> }
> 
> void getmax()
> {
> 	int head=0,tail=-1;
> 	for (register int i=0;i<m-1;i++)
> 	{
> 		while (head<=tail&&q[tail].val<a[i]) tail--;
> 		q[++tail].val=a[i],q[tail].pos=i;
> 	}
> 	for (register int i=m-1;i<n;i++)
> 	{
> 		while (head<=tail&&i-q[head].pos>=m) head++;
> 		while (head<=tail&&q[tail].val<a[i]) tail--;
> 		q[++tail].val=a[i],q[tail].pos=i;
> 		printf("%d ",q[head].val);
> 	}
> 	printf("\n");
> }
> 
> int main()
> {
> 	scanf("%d%d",&n,&m);
> 	for (register int i=0;i<n;i++) scanf("%d",&a[i]);
> 	getmin(),getmax();
> 	return 0;
> }

Home Page Go Back To top