题解 P2251 【质量检测】

JJJJones_Zhu · 2018-07-19 22:00:15 · 题解

RMQ！！！

这题数据水其实还可以，但肯定是不如1440了（这两题很像哦）1440 RMQ

但是！不同的是1440的数据到了2000000 但其实那题数据也很水

那题ST表最多拿到80分，而且毒瘤数据卡输入输出（雾。而这题只需要简单的ST表便可以处理，效率也是蛮高的，时间上根本不用担心，数据缩到了1000000会减去不少麻烦。

特地献上本 juruo 的ST表一份，请客官品尝

#include <iostream>
#include<algorithm>
#include<cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#define MAXN 1000005
using namespace std;
int dp[MAXN][25],i,N,M;
//dp[i][j]表示区间[i,i+2^j-1]的最小值。
inline void build()//ST表初始化，用到了DP思想
{
    for(int j = 1;j <= 20;++j)
    //倍增思想
    {
        for(i = 1;i <= M;++i)
            if(i+(1<<j)-1<=M)
                dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
                //状态转移方程
    }
}
int main()
{
    scanf("%d%d",&M,&N);
    //一定要改scanf和printf！！！血的教训！！！
    for(i=1;i<=M;++i)
        scanf("%d",&dp[i][0]);
        //dp[i][0]=第i个物品本身的质量，因为[i,i+2^0-1]这个区间长度为1，元素只有i本身。
    build();
    for(int op = 1;op <= M-N+1;++op){
        int k=log2(N);
        //k的值是[op,op+N-1]这个区间内最长的2的k次方的区间。
        printf("%d\n",min(dp[op][k],dp[op+N-1-(1<<k)+1][k]));}
    return 0;
}

倍增是很有价值的工具，掌握没有什么坏处

最后 juruo祝大家能在OI道路上越走越远～～