UVALive 6531 Go up the ultras 單調棧+RMQ
來源：程序員人生 發布時間：2014-12-05 09:04:10 閱讀次數：2147次
題目鏈接：點擊打開鏈接
題意：
給定n座山
下面n個數字表示n座山的高度
若這座山u合法，則要滿足：
1、若u的左側存在比u高的山，設v是u左側距離u最近的且嚴格比u高的山，在[v,u]之間最少有1座山x，使得x和u的高度差>=15000
2、右側也同理。
同時滿足1、2的情況則算合法。
問：
輸出所有合法的山。
思路：
求距離某個點最近的山就是保護1個單調棧，然后給山的高度求1個RMQ。
寫寫寫。。。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
template <class T>
inline bool rd(T &ret) {
char c; int sgn;
if(c=getchar(),c==EOF) return 0;
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?⑴:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
template <class T>
inline void pt(T x) {
if (x <0) {
putchar('-');
x = -x;
}
if(x>9) pt(x/10);
putchar(x%10+'0');
}
using namespace std;
typedef long long ll;
const int N = 100050;
int d[N*2][20];
void RMQ_init(int *A, int n) {
for (int i = 1; i <= n; ++i)
d[i][0] = A[i];
for (int j = 1; (1 << j) <= n; ++j)
for (int i = 1; i + j - 1 <= n; ++i) {
d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
}
}
int RMQ(int L, int R) {
int k = 0;
while ((1 << (k + 1)) <= R - L + 1)
++k;
return min(d[L][k], d[R - (1 << k) + 1][k]);
}
int n, h[N], Stack[N], top;
int lh[N], rh[N];
void work(){
for(int i = 1; i <= n; i++)rd(h[i]);
top = 0;
for(int i = 1; i <= n; i++) {
while(top && h[ Stack[top⑴] ] <= h[i])top--;
if(top) lh[i] = Stack[top⑴];
else lh[i] = 0;
Stack[top++] = i;
}
top = 0;
for(int i = n; i; i--){
while(top && h[ Stack[top⑴] ]<= h[i])top--;
if(top) rh[i] = Stack[top⑴];
else rh[i] = 0;
Stack[top++] = i;
}
}
const int hehe = 150000;
vector<int>ans;
int main(){
while(cin>>n){
work();
RMQ_init(h, n);
ans.clear();
for(int i =1; i <= n; i++){
if(lh[i] == 0 && rh[i] == 0) ans.push_back(i);
else if(lh[i] == 0){
int v = RMQ(i, rh[i]);
if(h[i] - v >= hehe)
ans.push_back(i);
}
else if(rh[i] == 0){
int v = RMQ(lh[i], i);
if(h[i] - v >= hehe)
ans.push_back(i);
}
else {
int u = RMQ(lh[i], i), v = RMQ(i, rh[i]);
int maxx = max(u, v);
if(h[i] - maxx >= hehe)
ans.push_back(i);
}
}
for(int i = 0; i < ans.size(); i++){
pt(ans[i]);
if(i==ans.size()⑴)puts("");
else putchar(' ');
}
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
