程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LA 6531 Go up the Ultras 單調棧+RMQ

LA 6531 Go up the Ultras 單調棧+RMQ

編輯:C++入門知識

LA 6531 Go up the Ultras 單調棧+RMQ


題意:已經懶得吐槽了。。有N個山峰,(N<=10^5),每個山峰有高度h,對應著每個山峰有一個d值,每個山峰到所有其他的嚴格比

它高的山峰都會經過一個最低值(山谷),d代表是h減去這些最低值中的最大值的差(如果不存在比它高的山峰那麼d就是它本身的

高度),問有多少山峰的d>=150000米。

思路:利用單調棧維護每個峰左邊第一個比它高的峰的位置l,右邊第一個比它高的峰的位置r,對於r,我們從前向後維護一個單調減

序列,如果當前考慮的點i比棧頂的元素高度高,那麼彈出棧頂元素,並將它的r置為i,直到棧頂元素的高度大於等於i的高度。對於l,

從後往前維護單調減序列。對於每個點,求[ l[ i ] , i ] 的最小值d1,[ i , r[ i ] ]的最小值d2,求個最大值d=max(d1,d2),然後看是否h[i]-

d>=150000,是就輸出,可以RMQ預處理一段區間的最小值,詳見代碼:

/*********************************************************
  file name: LA6531.cpp
  author : kereo
  create time:  2015年02月06日 星期五 17時00分19秒
*********************************************************/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=20;
const int MAXN=100000+50;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=100000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define PII pair
#define mk(x,y) make_pair((x),(y))
int n;
int dp[MAXN][N];
struct node{
    int l,r,h;
}p[MAXN];
stacks;
int RMQ(int l,int r){
    int k=0;
    while((1<<(k+1))<=r-l+1) k++;
    return min(dp[l][k],dp[r-(1<=p[i].h){
                s.push(i);
            }
            else{
                while(!s.empty() && p[s.top()].h=1;i--){
            if(s.empty())
                s.push(i);
            else if(p[s.top()].h>=p[i].h)
                s.push(i);
            else{
                while(!s.empty() && p[s.top()].h=150000){
                if(flag){
                    printf("%d",i);
                    flag=0;
                }
                else 
                    printf(" %d",i);
            }
        }
        printf("\n");
    }
	return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved