首页 » C++ » jzoj1370-飞船【RMQ初见】

jzoj1370-飞船【RMQ初见】

原文 http://blog.csdn.net/Mr_wuyongcong/article/details/79253383

2018-02-05 02:00:30阅读(568)

前言

RMQ就是一个在一个序列中来多次询问某段的最大值的快速的方法。其他自行度娘

正题 题目

一些成直线的星星,给出m段询问,求一段距离间最大的星星

输入输出与样例(建议无视) 输入

第一行输入N,M
接下来一行N个整数,表示星星的体积(1<=体积<=maxlongint)
接下来M行,每行两个整数L_i,R_i,表示询问区间。

输出

输出M行,每一行表示询问区间L_i到R_i之间最大星星的体积。

样例输入

6 3
5 7 3 9 2 10
1 3
2 4
3 6

样例输出

7
9
10

解题思路

就是暴力RMQ,这里讲一下RMQ。f[i][j]表示从i到i+2^j-1这个范围内的最大数。然后动态转移方程:F[i,j]=max(F[i,j-1],F[i+2^(j-1),j-1]),然后两个区间的元素个数都为2^x,所以[Li,Ri]的最大值为max(F[Li,X],F[Ri+1-2^x,X]),可以在O(E)内计算出来。

代码
#include<cstdio>
#include<cmath>
//开log用
#include<iostream>
using namespace std;
int f[100001][21],n,m,z,x,y;
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
      scanf("%d",&f[i][0]);//输出
    for (int j=1;(1<<j)<=n;j++)
      for (int i=1;i+(1<<j)-1<=n;i++)
      {
        f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
        //动态转移
      }
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        z=(int)(log(y-x+1)/log(2));//计算x
        printf("%d\n",max(f[x][z],f[y+1-(1<<z)][z]));//输出
    }
}

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹