单调队列：
#include<iostream>
using namespace std;
int N;
int h,t;
int que[26000];
int ind[26000];
bool empty()
{
if(h<=t) return 0;
else return 1;
}
int main()
{
scanf("%d",&N);
int x;
h=1; t=0;
int i=1;
while(scanf("%d",&x)&&x!=-1){
while(i-ind[h]+1>N&&!empty()) h++;
while(!empty()&&x>=que[t]) t--;
que[++t]=x;
if(i>=N) printf("%d\n",que[h]);
ind[t]=i++;
}
return 0;
}
线段树：
#include<iostream>
using namespace std;
struct arr{
int a,b;
int max;
}tree[100000];
int N,M;
int a[14001];
void build(int num,int la,int lb){
tree[num].a=la;
tree[num].b=lb;
if(la<lb){
int mid=(la+lb)>>1;
build(num<<1,la,mid);
build((num<<1)+1,mid+1,lb);
if(tree[num<<1].max>tree[(num<<1)+1].max)
tree[num].max=tree[num<<1].max;
else tree[num].max=tree[(num<<1)+1].max;
}
else tree[num].max=a[la];
}
void insert(int num,int la,int lb,int now){
if(tree[num].a==la&&tree[num].b==lb){
tree[num].max=now;
return;
}
int mid=(tree[num].a+tree[num].b)>>1;
if(lb<=mid)
insert(num<<1,la,lb,now);
else if(la>mid)
insert((num<<1)+1,la,lb,now);
if(tree[num<<1].max>tree[(num<<1)+1].max)
tree[num].max=tree[num<<1].max;
else tree[num].max=tree[(num<<1)+1].max;
}
int main()
{
scanf("%d",&N);
for(int i=1;i<=N;++i)
scanf("%d",&a[i]);
build(1,1,N);
M=N;
while(1){
printf("%d\n",tree[1].max);
scanf("%d",&a[0]);
if(a[0]==-1) break;
M++;
M=(M-1)%N+1;
insert(1,M,M,a[0]);
}
return 0;
}
posted on 2009-06-28 00:06
xfstart07 阅读(159)
评论(0) 编辑 收藏 引用