Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Why wrong?

Posted by zcl_wxy at 2005-12-14 08:24:31 on Problem 2559
我用的分治,为什么会错,请高人指点.
#include <stdio.h>
int hei[100001];
double getA(int l,int r)
{
    int i,j,k,cent,min,f;
    double s,sa=0.0,la,ra;
    if(l==r)  return hei[l];
    cent=(l+r)/2;
    la=getA(l,cent);
    if(sa<la)  sa=la;
    ra=getA(cent+1,r);
    if(sa<ra)  sa=ra;
    min=hei[cent];
    i=cent,j=cent+1;
    while(i>=l||j<=r)
    {
        f=0;
        while(i>=l&&hei[i]>=min)  { f=1;i--; }
        while(j<=r&&hei[j]>=min)  { f=1;j++; }
        if(!f)  break;
        s=(double)(j-i-1)*min;
        if(s>sa)  sa=s;
        if(i>=l)  min=hei[i];
        if(j<=r&&hei[j]>min)  min=hei[j];
    }    
    return sa;
}     
int main()
{
    int i,n;
    double area;
    while(scanf("%d",&n)==1)
    {
        if(n==0)  break;
        for(i=1;i<=n;i++)  scanf("%d",&hei[i]);
        area=getA(1,n);
        printf("%.0lf\n",area);
    }
    return 0;
} 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator