问题 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");

    }

}