UVALive 6531 Go up the ultras 单调栈+RMQ
来源：程序员人生 发布时间：2014-12-05 09:04:10 阅读次数：1978次
题目链接：点击打开链接
题意：
给定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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
