程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3410 && POJ 3776 Passing the Message 單調隊列

HDU 3410 && POJ 3776 Passing the Message 單調隊列

編輯：C++入門知識

題意：

給定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;
}


  1. 上一頁:
  2. 下一頁:
C++入門知識
hdu1568-Fibonacci

用到了斐波那契數列的通項公式。 先看對數的性質,log
C++對象模型那點事兒（成員篇）

1 前言 上篇提到了類的數據成員有兩種：stati
【原創】C++中對象的序列化，原創對象序列化

【原創】C++中對象的序列化，原創對象序列化　　1、對象序列
從匯編看c++中指向成員變量的指針(一)

  _x} _y}

HDU1687 Lucky Light [貪心]

  Lucky Light Time Lim
2013年 藍橋杯預賽 java 本科A 題目，藍橋預賽

2013年 藍橋杯預賽 java 本科A 題目，藍橋預賽1.
相關文章
閱讀排行榜
UVa 12086 Potentiometers 樹狀數組裸題 單點更新 區間查詢 Codeforces Round #246 (Div. 2) D. Prefixes and Suffixes(後綴數組orKMP) POJ 2411 Mondriaans Dream （狀態壓縮DP） Curling 2.0 (poj 3009 dfs) poj 1011 LeetCode 86 Partition List Usaco*Brownie Slicing，usacobrownie UVa 443 - Humble Numbers c++之虛函數的應用簡單講解 uvc攝像頭代碼解析2 asdfasdfasfasdfsadfsadfasdf，asdfasdfasdf
熱門圖文
[Laravel] Laravel的基本使用，laravel使用 C#2.0 新特性探究之委托與匿名委托 PHP獲取MAC地址 在J2EE環境中使用Quartz企業級計劃調度器（2） 深入分析ASP.NET Mvc 1.0 – 4. 使用ModelBinder綁定Action的參數 php 用header()讀寫csv文件方法 C#如何獲得 WINDOWS 版本 [並發並行]_[C/C++]_[使用線程本地存儲Thread Local Storage(TLS)調用復制文件接口的案例]
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved