Histogram LightOJ

题意：给出一个直方图，由n个长条组成，它们的x轴上坐标分别为1-n，读入n之后读入的一行中，第i个表示x轴上坐标为i的长条长度。求直方图最大的正方形面积。

方法：

核心是求出每个长条向左右可以"扩展"的最大长度。

法一：单调栈

将n个元素的编号依次入栈。每次入栈前，设要入栈的编号为x，对应长度为l，将栈顶的编号对应的长度大于等于l的所有编号出栈（由于此题的一些特性，将“大于等于”改为“大于”也可以使用，但这不是标准的单调栈）。这之后，栈顶元素就是x能扩展到的最左端的端点减1（注意，是减1）。对于某个元素，其出栈的那一刻，使其出栈的x减一就是其能扩展到的最右侧的端点。

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int T,n,ans,len;

 int st[],a[],l[],r[];

 void push(int idx)

 {

     while(len>&&a[st[len]]>=a[idx])    r[st[len--]]=idx-;

     l[idx]=st[len];

     st[++len]=idx;

 }

 int main()

 {

     int i,TT;

     scanf("%d",&T);

     for(TT=;TT<=T;TT++)

     {

         scanf("%d",&n);

         for(i=;i<=n;i++)

             scanf("%d",&a[i]);

         len=;

         ans=;

         for(i=;i<=n;i++)

             push(i);

         while(len>)    r[st[len--]]=n;

         for(i=;i<=n;i++)

             ans=max(ans,a[i]*(r[i]-l[i]));

         printf("Case %d: %d\n",TT,ans);

     }

     return ;

 }

(由于题目的某些特性，即使单调栈在push时不把相同的pop出来也可以过。然而正确的单调栈一般都要把相同的也pop出来)

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int T,n,ans,len;

 int st[],a[],l[],r[];

 void push(int idx)

 {

     while(len>&&a[st[len]]>a[idx])    r[st[len--]]=idx-;

     l[idx]=st[len];

     st[++len]=idx;

 }

 int main()

 {

     int i,TT;

     scanf("%d",&T);

     for(TT=;TT<=T;TT++)

     {

         scanf("%d",&n);

         for(i=;i<=n;i++)

             scanf("%d",&a[i]);

         len=;

         ans=;

         for(i=;i<=n;i++)

             push(i);

         while(len>)    r[st[len--]]=n;

         for(i=;i<=n;i++)

             ans=max(ans,a[i]*(r[i]-l[i]));

         printf("Case %d: %d\n",TT,ans);

     }

     return ;

 }

法二：奇奇怪怪的方法，类似链表/kmp的预处理

left[i]和right[i]分别表示能扩展到的最左/右侧的高度小于等于它的长条的编号。看起来可能很慢，但是实际上均摊复杂度O(n)。

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int T,n,ans;

 int a[],left[],right[];

 int main()

 {

     int TT,i;

     scanf("%d",&T);

     for(TT=;TT<=T;TT++)

     {

         ans=;

         scanf("%d",&n);

         for(i=;i<=n;i++)

             scanf("%d",&a[i]);

         for(i=;i<=n;i++)

         {

             left[i]=i;

             while(left[i]>&&a[left[i]-]>=a[i])    left[i]=left[left[i]-];

         }

         for(i=n;i>=;i--)

         {

             right[i]=i;

             while(right[i]<n&&a[right[i]+]>=a[i])    right[i]=right[right[i]+];

         }

         for(i=;i<=n;i++)

             ans=max(ans,a[i]*(right[i]-left[i]+));

         printf("Case %d: %d\n",TT,ans);

     }

 }

法三：一个区间由区间最小值控制。对于某一个区间，答案要么包含这个最小值，要么在最小值左侧区间取，要么在右侧区间取。因此预处理解决RMQ，然后分治解决。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int T,TT,n;

 int minn[][],a[];

 int query(int l,int r)

 {

     int k=;

     while((<<(k+))<=r-l+)    ++k;

     return a[minn[k][l]]>a[minn[k][r-(<<k)+]]?minn[k][r-(<<k)+]:minn[k][l];

 }

 int get(int l,int r)

 {

     if(l>r)    return ;

     if(l==r)

         return a[l];

     int pos=query(l,r);

     return max(max(get(l,pos-),get(pos+,r)),a[pos]*(r-l+));

 }

 int main()

 {

     int i,j;

     scanf("%d",&T);

     for(TT=;TT<=T;TT++)

     {

         memset(minn,,sizeof(minn));

         memset(a,,sizeof(a));

         scanf("%d",&n);

         for(i=;i<=n;i++)

             scanf("%d",&a[i]);

         for(i=;i<=n;i++)

             minn[][i]=i;

         for(i=;(<<i)<=n;i++)

             for(j=;j<=n-(<<i)+;j++)

                 minn[i][j]=a[minn[i-][j]]>a[minn[i-][j+(<<(i-))]]?minn[i-][j+(<<(i-))]:minn[i-][j];

         printf("Case %d: %d\n",TT,get(,n));

     }

     return ;

 }

巴特西

Histogram LightOJ - 1083

最新文章

热门文章