Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:单调队列

Posted by 0_8 at 2018-12-15 16:52:03 on Problem 2823
In Reply To:单调队列 Posted by:hntby at 2018-12-15 11:09:57
> #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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator