UvaLive 6531 Go up the ultras DP+RMQ
來源：程序員人生 發(fā)布時(shí)間：2014-09-29 09:19:27 閱讀次數(shù)：2864次
鏈接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4542
題意：有N個(gè)山峰，(N<=10^5)，每個(gè)山峰有高度h，對(duì)應(yīng)著每個(gè)山峰有一個(gè)d值，每個(gè)山峰到所有其他的嚴(yán)格比它高的山峰都會(huì)經(jīng)過一個(gè)最低值（山谷），d代表是h減去這些最低值中的最大值的差（如果不存在比它高的山峰那么d就是它本身的高度），問有多少山峰的d>=150000米。
思路：題讀起來還是蠻有難度的，對(duì)于山峰p，題目所要求的d的值所需要的最高的山谷一定出現(xiàn)在這p與和它相鄰的兩個(gè)比它高的山峰之間。這樣問題就轉(zhuǎn)化成了確定兩邊第一個(gè)比它高的山峰，并找到這兩個(gè)之間的最小值（山谷）。找到第一個(gè)比它高的山峰用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("
");
}
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
