问题 B: 奶牛排队

时间限制: 1 Sec 内存限制: 128 MB
提交: 13 解决: 9
[提交][状态][讨论版][命题人:add_wjl][Edit] [TestData]

题目链接：http://acm.ocrosoft.com/problem.php?cid=1689&pid=1

题目描述

每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是为了避免水平悬殊,牛的身高不应该相差太大. John 准备了Q (1 <= Q <= 180,000) 个可能的牛的选择和所有牛的身高 (1 <= 身高 <= 1,000,000). 他想知道每一组里面最高和最低的牛的身高差别. 注意: 在最大数据上, 输入和输出将占用大部分运行时间.

输入

* 第一行: N 和 Q. * 第2..N+1行: 第i+1行是第i头牛的身高.

* 第N+2..N+Q+1行: 两个整数, A 和 B (1 <= A <= B <= N), 表示从A到B的所有牛.

输出

*第1..Q行: 所有询问的回答 (最高和最低的牛的身高差), 每行一个.

样例输入

样例输出

思路：建一个dp[i][j],i表示从i的位置开始扫描，j表示从i开始（i也包括）往后扫描（1<<j）个数

然后直接RMQ算法，输出的时候优化一下就行了。

代码：

#include<bits/stdc++.h>

using namespace std;

int n;

int dp_max[100005][30];//动态规划 ，dp[i][j],j的意思是1<<j(扫描的个数)！！  j的意思是1<<j(扫描的个数)！！  j的意思是1<<j(扫描的个数)！！ 重要的事情说3遍！！！

int dp_min[100005][30];

int a[100005];//用于存储数字

void st_max(int m)//初始化dp

{

    for (int i = 1; i <= m; i++)

    {

        dp_max[i][0] = a[i];//j位置为0时，相当于1<<0=1,所以在范围为1的区间里的最值就是a[i]

    }

    for (int j = 1; (1 << j) <= m; j++)

    {

        for (int i = 1; i + (1 << j) - 1 <= m; i++)

        {

            dp_max[i][j] = max(dp_max[i][j - 1], dp_max[i + (1 << (j - 1))][j - 1]);

            //这里不太好解释，就是比如i到i+(1<<j)-1个数分为2组，一组是i到 i+(1<<(j-1))-1，另一组是 i+(1<<(j-1))到i+(1<<j)-1，进行动态规划

        }

    }

}

int rmq_max(int l, int r)//取l到r区间里的最值

{

    int k = 0;

    while ((1 << (k + 1)) <= r - l + 1)k++;//找到某个k可以让2块长为（1<<k）的区间将l到r的区间完全覆盖

    return max(dp_max[l][ k], dp_max[r- (1 << k)+1][ k]);//取最值

}

void st_min(int m)//和上面几乎一样

{

    for (int i = 1; i <= m; i++)

    {

        dp_min[i][0] = a[i];

    }

    for (int j = 1; (1 << j) <= m; j++)

    {

        for (int i = 1; i + (1 << j)-1 <= m; i++)

        {

            dp_min[i][j] = min(dp_min[i][j - 1], dp_min[i + (1 << (j - 1))][j - 1]);

        }

    }

}

int rmq_min(int l, int r)

{

    int k = 0;

    while ((1 << (k + 1)) <= r-l+1)k++;

    return min(dp_min[l][k], dp_min[r - (1 << (k)) + 1][k]);

}

int main()

{

    int n;

    scanf("%d", &n);

    int k;

    scanf("%d", &k);

    for (int i = 1; i <= n; i++)

    {

        scanf("%d", &a[i]);

    }

    st_max(n);

    st_min(n);

    for(int i=1;i<=k;i++)//套板子即可

    {

        int xx,yy;

        scanf("%d%d",&xx,&yy);

        printf("%d\n",rmq_max(xx,yy)-rmq_min(xx,yy));

            //cout<<rmq_max(xx,yy)<<endl;

       }

  

}