问道ACM题,Problem DescriptionGiven a number sequence A with n numbers,you task is to find the max A[i]-A[j] which i

来源：学生作业帮助网编辑：作业帮时间：2024/05/06 20:37:11

问道ACM题,Problem DescriptionGiven a number sequence A with n numbers,you task is to find the max A[i]-A[j] which i
问道ACM题,
Problem Description
Given a number sequence A with n numbers,you task is to find the max A[i]-A[j] which i

这一道题可以用求区间最值的方法解决主要就是RMQ和线段树或树状数组算法,参考http://baike.baidu.com/link?url=ag6ty7JO80bNLjm4ZvfWL7jQbgfukKQRP6ogfTC8-XjmNJOcL6UOgd2hSw_ht1qG2bSZR8tL-vM5noff-BFiPK#4_3.

代码：

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<sstream>
#include<cstring>
#include<math.h>
#include<stdio.h>
#include<map>
#include<set>
using namespace std;
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#define MN 100005
int mi[MN][17],mx[MN][17],w[MN];
int n;
void rmqinit()
{
int i,j,m;
for(i=1;i<=n;i++){mi[i][0]=mx[i][0]=w[i];}
m=int(log(n)/log(2.0));
for(i=1;i<=m;i++)
{
for(j=n;j>=1;j--)
{
mx[j][i]=mx[j][i-1];
if(j+(1<<(i-1))<=n)
mx[j][i]=max(mx[j][i],mx[j+(1<<(i-1))][i-1]);
mi[j][i]=mi[j][i-1];
if(j+(1<<(i-1)<=n))
mi[j][i]=min(mi[j][i],mi[j+(1<<(i-1))][i-1]);
}
}
}

int rmqmin(int l,int r)
{
int m=int(log(r-l+1)/log(2.0));
return min(mi[l][m],mi[r-(1<<m)+1][m]);
}

int rmqmax(int l,int r)
{
int m=int(log(r-l+1)/log(2.0));
return max(mx[l][m],mx[r-(1<<m)+1][m]);
}

int main()
{
int i,T=1;
while(cin>>n){
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);//cin>>w[i];
rmqinit();
int ans=w[1]-w[2];
int tmp;
for(i=2;i<=n-1;i++){
tmp=rmqmax(1,i)-rmqmin(i+1,n);
if(tmp>ans)
ans=tmp;
}
printf("Case %d: %d\n",T++,ans);
}
return 0;
}

问道ACM题,Problem DescriptionGiven a number sequence A with n numbers,you task is to find the max A[i]-A[j] which i 问道题! c语言acm题 acm刷题是什么意思问道怎样写题, 问道立体几何的题问道三角函数的题, 北大ACM 1993题!快要交了..实在做不出来..有没有哪位能帮忙下...谢谢啦!程序正确追加100分!绝对!题目:http://acm.pku.edu.cn/JudgeOnline/problem?id=1993 问道高中数列基础题问道什么叫位列仙班?如题杭电ACM problem 1002 A + B Problem II为什么会WRONG ANSWER?计算结果没错啊?#include ACM中的一题找素数Problem Description对于表达式n^2+n+41,当n在（x,y）范围内取整数值时（包括x,y）(-39 杭电acm 2035 题的算法是怎样的,杭电acm 2035 题的算法是怎样的,我要算法分析,不要代码!Problem Description求A^B的最后三位数表示的整数.说明：A^B的含义是“A的B次方”Input输入数据包含多个测试实杭电ACM题1114.把并代码写一下给我,最好再写一下解决的方法说明.我懒得写.貌似挺简单的,帮个忙,谢了Problem DescriptionBefore ACM can do anything, a budget must be prepared and the necessary financial support obtained ACM题中的Rails题题意是什么? pku ACM题翻译在哪找? ACM竞赛中谈到AC了题, c语言 ACM一题Problem DescriptionContest time again!How excited it is to see balloons floating around.But to tell you a secret,the judges' favorite time is guessing the most popular problem.When the contest is over,they will count the balloons of