首页 > 代码库 > UVALive 6531 Go up the ultras 单调栈+RMQ
UVALive 6531 Go up the ultras 单调栈+RMQ
题目链接:点击打开链接
题意:
给定n座山
下面n个数字表示n座山的高度
若这座山u合法,则要满足:
1、若u的左边存在比u高的山,设v是u左边距离u最近的且严格比u高的山,在[v,u]之间至少有一座山x,使得x和u的高度差>=15000
2、右边也同理。
同时满足1、2的情况则算合法。
问:
输出所有合法的山。
思路:
求距离某个点最近的山就是维护一个单调栈,然后给山的高度求一个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: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-1] ] <= h[i])top--; if(top) lh[i] = Stack[top-1]; else lh[i] = 0; Stack[top++] = i; } top = 0; for(int i = n; i; i--){ while(top && h[ Stack[top-1] ]<= h[i])top--; if(top) rh[i] = Stack[top-1]; 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()-1)puts(""); else putchar(' '); } } return 0; }
UVALive 6531 Go up the ultras 单调栈+RMQ
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。