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

求救~~DEV都过了,却是无限次的CE,囧!!!

Posted by 2322 at 2011-01-19 21:36:52 on Problem 2823
#include<stdio.h>
#include<malloc.h>
#define Max 1000005
struct tree
{
     int b,e;
     int min,max;
     struct tree *lchild,*rchild;    
};
int a[Max];
struct tree * build(int b,int e)
{
      struct tree *root=(struct tree*)malloc(sizeof(struct tree));
       int mid;
      if(b == e)
      {
            root->b=root->e=e;
            root->min=root->max=a[b];
            root->lchild=root->rchild=NULL; 
            return root;   
      }    
     
      mid=(int)(b+e)/2;
      root->b=b;
      root->e=e;
      root->lchild=build(b,mid);
      root->rchild=build(mid+1,e);
      root->min=root->lchild->min >  root->rchild->min ?  root->rchild->min :root->lchild->min;
      root->max=root->lchild->max > root->rchild->max ? root->lchild->max : root->rchild->max;
      return root;    
      
}

int find_max(int b,int e,struct tree * root)
{
      if(root == NULL)
           return -32768;
      if(b > root->e  || e < root->b)
           return -32768;
      if(b <= root->b && e >= root->e)
             return root->max;
      int maxl=find_max(b,e,root->lchild);
      int maxr=find_max(b,e,root->rchild);
      if(maxl > maxr)
           return maxl;
      return maxr;        
}
int find_min(int b,int e,struct tree *root)
{
       if(root == NULL)
           return 32767;
       if(e < root->b  || b > root->e)
           return 32767;
       if(b <= root->b && e >= root->e)
           return root->min;
       int minl=find_min(b,e,root->lchild); 
       int minr=find_min(b,e,root->rchild);
       if(minl < minr)
           return minl;
       return minr;    
 }
 int main()
 {
         int i,j;
         int num,step;
         int min,max;
         scanf("%d%d",&num,&step);
         i=0;
         while(i<num)
             scanf("%d",&a[i++]);
         struct tree * root=build(0,num-1);
         for(i=0;i<=num-step;i++)
         {
              min=find_min(i,i+step-1,root);
              max=find_max(i,i+step-1,root);
              printf("%d ",min);
              a[i]=max;  
               
         } 
         printf("\n");
         for(i=0;i<=num-step;i++)
             printf("%d ",a[i]);
         printf("\n");
         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