首页 > 代码库 > UvaLive 6531 Go up the ultras
UvaLive 6531 Go up the ultras
链接:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4542
题意:有N个山峰,(N<=10^5),每个山峰有高度h,对应着每个山峰有一个d值,每个山峰到所有其他的严格比它高的山峰都会经过一个最低值(山谷),d代表是h减去这些最低值中的最大值的差(如果不存在比它高的山峰那么d就是它本身的高度),问有多少山峰的d>=150000米。
思路:题读起来还是蛮有难度的,对于山峰p,题目所要求的d的值所需要的最高的山谷一定出现在这p与和它相邻的两个比它高的山峰之间。这样问题就转化成了确定两边第一个比它高的山峰,并找到这两个之间的最小值(山谷)。找到第一个比它高的山峰用dp,询问最小值用rmq。
代码:
#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <ctype.h> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> #define eps 1e-8 #define INF 0x7fffffff #define maxn 100005 #define PI acos(-1.0) #define seed 31//131,1313 #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r typedef long long LL; typedef unsigned long long ULL; using namespace std; int val[maxn*4],aa[maxn]; int t; void build(int i,int l,int r) { if(l==r) { scanf("%d",&val[i]); aa[l]=val[i]; return ; } int mid=(l+r)>>1; build(lson),build(rson); val[i]=min(val[i<<1],val[i<<1|1]); } int query(int i,int l,int r,int q_l,int q_r) { if(q_l<=l&&r<=q_r) return val[i]; int mid=(l+r)>>1; if(q_r<=mid) return query(lson,q_l,q_r); else if(q_l>mid) return query(rson,q_l,q_r); else return min(query(rson,mid+1,q_r),query(lson,q_l,mid)); } int L[maxn],R[maxn]; void init() { memset(L,0,sizeof(L)); memset(R,0,sizeof(R)); memset(aa,-1,sizeof(aa)); memset(val,0,sizeof(val)); build(1,1,t); } int main() { while(~scanf("%d",&t)) { init(); L[1]=0; for(int i=2; i<=t; i++) { if(aa[i-1]>aa[i]) L[i]=i-1; else { int from=i-1; while(aa[i]>=aa[L[from]]&&from!=0) from=L[from]; L[i]=from; } } R[t]=t+1; for(int i=t-1;i>=1;i--) { if(aa[i+1]>aa[i]) R[i]=i+1; else { int from=i+1; while(aa[i]>=aa[R[from]]&&from!=t+1) from=R[from]; R[i]=from; } } bool flag=0; for(int i=1; i<=t; i++) { int res=-1; if(query(1,1,t,L[i],i)>res&&L[i]!=0) res=query(1,1,t,L[i],i); if(query(1,1,t,i,R[i])>res&&R[i]!=t+1) res=query(1,1,t,i,R[i]); if((res==-1&&aa[i]>=150000)||(aa[i]-res>=150000)) { if(flag==0) { printf("%d",i); flag = 1; } else printf(" %d",i); } } printf("\n"); } return 0; }
UvaLive 6531 Go up the ultras
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。