频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
HDU 3410 && POJ 3776 Passing the Message 单调队列
2014-04-30 11:11:36         来源:HDU 3410 && POJ 3776 Passing the Message 单调队列  
收藏   我要投稿

题意:

给定n长的数组(下标从1-n)(n个人的身高,身高各不相同

问:对于第i个人,他能看到的左边最矮的人下标。(如果这个最矮的人被挡住了,则这个值为0)

还有右边最高的人下标,同理若被挡住了则这个值为0

输出n行,每个人左右2边的下标。

单调队列,对于 front - rear 的队列(注意出队都是在rear,入队也是在rear)

当加入元素x,若这队列是单调递增的,显然q.front() <= x , 反之若>x ,则把队首元素弹掉,这样就能保持单调性。

若弹掉了队首元素,在此题中就相当于最矮的人被挡住了,因为{q.end() < q.front() }> x。


#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define N 50010
int l[N], r[N];
int a[N],n;
int L,R;
int q[N*2];
int pos[N];
void init(){ L=1;R=0; }

void work1(){
	init();
	for(int i = 1; i <= n; i++){
		bool fa = false;
		while(L<=R && q[R]mp;
int Stack[N];
int main(){
	int i,j ,u, v, T, Cas = 1;
	scanf("%d",&T);
	while(T--){
		mp.clear();
		scanf("%d",&n);
		for(i=1;i<=n;i++)scanf("%d",&a[i]);
		work1();
		work2();
		printf("Case %d:\n",Cas++);
		for(int i = 1;i <=n; i++)printf("%d %d\n",l[i],r[i]);
	}
	return 0;
}


点击复制链接 与好友分享!回本站首页
相关TAG标签 队列
上一篇:C++ new函数的背后
下一篇:浅谈ARM9的LCD驱动
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站