#include<iostream>
#include<stdio.h>
using namespace std;
struct Node
{
	int v,ind;
	Node *next,*pre;
};

Node *H1,*T1;
Node *H2,*T2;
Node N1[1<<20];
Node N2[1<<20];
int result[1<<20];
int n,k;

void init()
{
	scanf("%d%d",&n,&k);
	scanf("%d",&N1[0].v);
	N2[0].v=N1[0].v;
	N2[0].ind=N1[0].ind=0;
	N1[0].next=NULL;
	N1[0].pre=NULL;
	H1=&N1[0];T1=&N1[0];
	N2[0].next=NULL;
	N2[0].pre=NULL;
	H2=&N2[0];T2=&N2[0];
}
void insert1(int i)
{
	N1[i].pre=NULL;
	N1[i].next=H1;
	H1->pre=&N1[i];
	H1=&N1[i];
}
void insert2(int i)
{
	N2[i].pre=NULL;
	N2[i].next=H2;
	H2->pre=&N2[i];
	H2=&N2[i];
}
void del1(int i)
{
	if (N1[i].next==NULL)
	{
		T1=N1[i].pre;
		N1[i].pre->next=NULL;
	}
	else
	{
		N1[i].pre->next=N1[i].next;
		N1[i].next->pre=N1[i].pre;
	}
}
void del2(int i)
{
	if (N2[i].next==NULL)
	{
		T2=N2[i].pre;
		N2[i].pre->next=NULL;
	}
	else
	{
		N2[i].pre->next=N2[i].next;
		N2[i].next->pre=N2[i].pre;
	}
}
void get_ans()
{
	int i,j;
	for (i=1;i<k-1;i++)
	{
		scanf("%d",&N1[i].v);
		N1[i].ind=i;
		N2[i].ind=i;
		N2[i].v=N1[i].v;
		insert1(i);
		insert2(i);
		Node *tmp=N1[i].next;
		while (tmp!=NULL)
			if (tmp->v>=N1[i].v)
			{
				del1(tmp->ind);
				tmp=tmp->next;
			}
			else break;
		tmp=N2[i].next;
		while (tmp!=NULL)
			if (tmp->v<=N2[i].v)
			{
				del2(tmp->ind);
				tmp=tmp->next;
			}
			else break;
	}

	for (i=k-1;i<n;i++)
	{
		scanf("%d",&N1[i].v);
		N1[i].ind=i;
		N2[i].ind=i;
		N2[i].v=N1[i].v;
		insert1(i);
		Node *tmp=N1[i].next;
		while (tmp!=NULL)
			if (tmp->v>=N1[i].v)
			{
				del1(tmp->ind);
				tmp=tmp->next;
			}
			else break;
		if (i==n-1) printf("%d\n",T1->v);
		else printf("%d ",T1->v);
		if (T1->ind==i-k+1)
			del1(T1->ind);

		insert2(i);
		tmp=N2[i].next;
		while (tmp!=NULL)
			if (tmp->v<=N2[i].v)
			{
				del2(tmp->ind);
				tmp=tmp->next;
			}
			else break;
		result[i-k+1]=T2->v;
		if (T2->ind==i-k+1)
			del2(T2->ind);
		
	}
	for (i=0;i<n-k+1;i++)
		if (i)
			printf(" %d",result[i]);
		else 
			printf("%d",result[0]);
	printf("\n");
}

int main()
{
	init();
	get_ans();
}

• 指针操作太多了吧！ (2461) Sempr 2006-07-03 23:16:22
• 算法对了，就一定不会超时么？ (2461) sunmoonstar 2006-07-04 03:13:40
• 2N也是O(N),99999999N也是O(N) (2461) tdzl2OO3 2006-08-04 11:48:40