问题 D: 最敏捷的机器人

问题 D: 最敏捷的机器人

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

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

题目描述

Wind设计了很多机器人。但是它们都认为自己是最强的，于是，一场比赛开始了~ 

机器人们都想知道谁是最敏捷的，于是它们进行了如下一个比赛。 首先，它们面前会有一排共n个数，它们比赛看谁能最先把每连续k个数中最大和最小值写下来，当然，这些机器人运算速度都很快，它们比赛的是谁写的更快。

但是Wind也想知道答案，你能帮助他吗？ 

输入

第一行为n，k两个数,(1<=k<=n<=100 000)。

第二行共n个数，为数字序列，所有数字均在longint范围内。

输出

共 n-k+1 行。

第 i 行为第 i~i+k-1 这 k 个数中的最大和最小值。

样例输入

5 3

1 2 3 4 5

样例输出

3 1

4 2

5 3

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

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

代码：

#include<bits/stdc++.h>

using namespace std;

int n;

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

int dp_min[1000005][30];

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

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_min(n);

    st_max(n);

    //这里就是输出答案时的优化，还有输出用printf，又被cout卡时间了！！！！！！

    //假如你已经有了某个区间的最值，并且这个区间起点不是最值，那么下个区间的最值只需要用新加进来的元素和原来的最值比对，否则重新RMQ跑一遍

    int maxx=rmq_max(1, 1 + k - 1);// 有了第一个区间的最值

    int minn=rmq_min(1, 1 + k - 1);

    cout<<maxx<<" ";cout<<minn<<" "<<endl;

    for(int i=2;i<=n-k+1;i++)

    {

        if(a[i-1]==maxx)//假如这个区间的最值就是第一个数，那算后一个区间就要RMQ重新跑一遍

        {

            printf("%d ",rmq_max(i, i + k - 1));

           // cout << rmq_max(i, i + k - 1) << " ";

            maxx=rmq_max(i, i + k - 1);//重新记录最值

        }

        else

        {

            maxx=max(maxx,a[i+k-1]);// 新区间的最值只需要用新加进来的元素和原来的最值比对

            printf("%d ",maxx);

            //cout<<maxx<<" ";

        } if(a[i-1]==minn)//和上面一样

        {

            printf("%d ",rmq_min(i, i + k - 1));

            //cout << rmq_min(i, i + k - 1) << " ";

            minn=rmq_min(i, i + k - 1);

        }

        else

        {

            minn=min(minn,a[i+k-1]);

            printf("%d ",minn);

            //cout<<minn<<" ";

        }

        printf("\n");

    }

}