hyfhaha @ 2018-08-02 08:59:28
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int fmax_[310101][33],fmin_[310101][33],s,n,m,p,x,y;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&s);
fmax_[i][0]=s;
fmin_[i][0]=s;
}
//O(nlogn)预处理 DP、倍增思想
for(int j=1;j<=(int)(log2(n));j++) //j表示区间长度为2^j
{
for(int i=1;i<=n-(1<<j)+1;i++) //i表示区间开始点
{
fmax_[i][j]=max(fmax_[i][j-1],fmax_[i+(1<<(j-1))][j-1]); //转移方程f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1])
fmin_[i][j]=min(fmin_[i][j-1],fmin_[i+(1<<(j-1))][j-1]); //转移方程f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1])
}
}
//O(1)查询
for(int i=1;i<=n-m+1;i++)
{
x=i;y=i+m-1;
if(y-x+1<=0)
p=0;
else
p=(int)(log2(y-x+1));
printf("%d ",min(fmin_[x][p],fmin_[y-(1<<p)+1][p]));
}
printf("\n");
for(int i=1;i<=n-m+1;i++)
{
x=i;y=i+m-1;
if(y-x+1<=0)
p=0;
else
p=(int)(log2(y-x+1));
printf("%d ",max(fmax_[x][p],fmax_[y-(1<<p)+1][p]));
}
return 0;
}
敢问为什么RE??? 60分
by CreeperK @ 2018-08-08 10:00:06
还有就是本题可以只用两个一维数组(因为长度是固定的)