HDU 3486 Interviewe - botaowudi - 博客园

原题链接:Interviewe(hdoj/hdu3486) ?
文章价值(3) ?
阅读数(160) ?

HDU 3486 Interviewe

该题是一道RMQ+二分

RMQ(Range?Minimum/Maximum?Query)问题是求区间最值问题。你当然可以写个O(n)的(怎么写都可以吧=_=),但是万一要询问最值1000000遍,估计你就要挂了。这时候你可以放心地写一个线段树(前提是不写错)Ologn)的复杂度应该不会挂。但是,这里有更牛的算法,就是ST算法,它可以做到O(nlogn)的预处理,O(1)!!!地回答每个询问。

  来看一下ST算法是怎么实现的(以最大值为例):

  首先是预处理,用一个DP解决。设a是要求区间最值的数列,f表示从第i个数起连续2^j个数中的最大值。例如数列3?2?4?5?6?8?1?2?9?7?,f[10]表示第1个数起,长度为2^0=1的最大值,其实就是3这个数。f[12]=5f[13]=8f[20]=2f[21]=4……从这里可以看出f其实就等于a。这样,Dp的状态、初值都已经有了,剩下的就是状态转移方程。我们把f平均分成两段(因为f一定是偶数个数字),从ii+2^(j-1)-1为一段,i+2^(j-1)i+2^j-1为一段(长度都为2^j-1)。用上例说明,当i=1j=3时就是3,2,4,5?和?6,8,1,2这两段。f就是这两段的最大值中的最大值。于是我们得到了动规方程F=maxF,F.

  接下来是得出最值,也许你想不到计算出f有什么用处,一般毛想想计算max还是要O(logn),甚至O(n)。但有一个很好的办法,做到了O1)。还是分开来。如在上例中我们要求区间[28]的最大值,就要把它分成[2,5][5,8]两个区间,因为这两个区间的最大值我们可以直接由f[22]f[52]得到。扩展到一般情况,就是把区间[lr]分成两个长度为2^n的区间(保证有f对应)。直接给出表达式:

  k:=ln(l(r-l+1)/ln(2));

  ans:=max(F[lk],F[r-2^k+1,k]);

这道题如果不用二分就会TLE。

?

#include
#include
#include
#include
using namespace std;
int dp_max[20][200024];
class RMQ
{
public:
int n,value;

int num[200024];

int S;
inline int max( int a,int b )
{
return a>b?a:b;
}
void get_RMQ( );
int result(int ,int );
bool input( );
bool compare();
int RMQ_result(int pre,int mid);
};
bool RMQ::input( )
{
scanf( "%d%d",&n,&value );
if( n<0||value<0 ) return false;
S=0;
for( int i=1; i<=n ; i++ )
{
scanf( "%d" ,&num[i] );
S+=num[i];
}
return true;
}
void RMQ::get_RMQ( )
{
int t=( int )( log( double( n ) )/log( 2.0 ) );
for( int i=1;i <= n; i++ )
{
dp_max[0][i] = num[ i ];
}

for( int j=1; j<= t ; j++ )
{
for( int i = 1; i + ( 1<1<=n; i++ )
{//printf( "%d %d afsaf",j,t );
dp_max[j][i] = max( dp_max[j-1][i] , dp_max[j-1][i+( 1<<(j-1) )] );
}

}
}
int RMQ::result( int left ,int right )
{

int t=( int )( log( ( double )(right -left+1 ) )/log( 2.0 ) );
return max( dp_max[t][left] , dp_max[t ][ right-( 1<1 ] );
}
int RMQ::RMQ_result( int pre,int mid )
{
int ans=0;
for( int i=1;i<=mid;i++ )
{
ans+=result( ( i-1 )*pre+1,i*pre );
}
return ans;
}
bool RMQ::compare( )
{
if( value>S )
{
printf( "-1\n" );
return false;
}
return true;
}
int main()
{
RMQ a;
while( a.input( ) )
{
if( a.compare( ) )
{
a.get_RMQ();
int l=1,r=a.n,mid,ans=0;
while( l<=r )
{
mid=( l+r )/2;
int pre=a.n/mid;
int t=a.RMQ_result( pre,mid );
if( t>a.value )
{
r=mid-1;
ans=mid;
}
else l=mid+1;
}
// printf( "afsaf" );
printf( "%d\n",ans );
}
}
return 0;
}


posted @ 2012-01-06 12:02 botaowudi 阅读(...) 评论(...) 编辑 收藏




(注:此网站文章大都来自公开的博客,如有原作者发现有侵权问题,请在此留言,我们会立刻删除相关文章。)

我的评价: