百度之星 2005年 初赛题目二

题目描述：请编写程序，找出下面 “ 输入数据及格式 ” 中所描述的输入数据文件中最大重叠区间的大小。

对一个正整数 n ，如果 n 在数据文件中某行的两个正整数（假设为 A 和 B ）之间，即 A<=n<=B 或 A>=n>=B ，则 n 属于该行；如果 n 同时属于行 i 和 j ，则 i 和 j 有重叠区间；重叠区间的大小是同时属于行 i 和 j 的整数个数。
例如，行（ 10 20 ）和（ 12 25 ）的重叠区间为 [12 20] ，其大小为 9 ；行（ 20 10 ）和（ 12 18 ）的重叠区间为 [10 12] ，其大小为 3 ；行 (20 10) 和（ 20 30 ）的重叠区间大小为 1 。

输入数据：程序读入已被命名为 input.txt 的输入数据文本文件，该文件的行数在 1 到 1,000,000 之间，每行有用一个空格分隔的 2 个正整数，这 2 个正整数的大小次序随机，每个数都在 1 和 2^32-1 之间。（为便于调试，您可下载测试 input.txt 文件，实际运行时我们会使用不同内容的输入文件。）

输出数据：在标准输出上打印出输入数据文件中最大重叠区间的大小，如果所有行都没有重叠区间，则输出 0 。

评分标准：程序输出结果必须正确，内存使用必须不超过 256MB ，程序的执行时间越快越好。

 

 

 

l2lib.c

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

struct Node
{
       int LineNum;
       int Begin;
       int End;
       int Len;
       struct Node * Next;
};


struct List
{
     struct Node * Header;
     int Len;
     struct Node * CurPtr;
     int CurPos;
};

void InitList(struct List* list);
void AddList(struct List* list,int linenum,int start,int end);
void FreeList(struct List* list);
void FilterList(struct List* list,int filter); //剔除|end-start|<filter的节点
int GetMaxOverRange(struct List* list,int a,int b);//获取a,b与List节点重叠区域最大的值
void PrintList(struct List* list); //打印列表
int GetLen(struct List* list);

 

 

   l2lib.c

 

#include "l2lib.h"
void InitList(struct List* list)
{
     list->Header=NULL;
     list->Len=0;
     list->CurPtr=NULL;
     list->CurPos=0;
}
void AddList(struct List* list,int linenum,int start,int end)
{
     struct Node* node = (struct Node*)malloc(sizeof(struct Node));
     node->LineNum=linenum;
     node->Begin=start;
     node->End=end;
     node->Len=abs(end-start);

     node->Next=list->Header;
     list->Header=node;
     list->Len++;
}
void FreeList(struct List* list)
{
     struct Node* tmp;
     while(list->Header!=NULL)
     {
        tmp=list->Header;
        list->Header=tmp->Next;
        free(tmp);
        list->Len--;
     }
}
void FilterList(struct List* list,int filter)
{
 	 struct Node* tmp;
 	 struct Node* cur;
 	 while(list->Header!=NULL&&list->Header->Len<filter)
 	 {
		 tmp=list->Header;
		 list->Header=tmp->Next;
		 free(tmp);
		 list->Len--;
	 }
 	 cur=list->Header;
 	 while(cur->Next != NULL)
 	 {
	    tmp=cur->Next;
	    //printf("line:%d\n",cur->LineNum);
	    if((int)((struct Node*)(cur->Next)->Len)<filter)
	    {
	       cur->Next=(struct Node*)(cur->Next)->Next;
	       (int)(list->Len)--;
	       free(tmp);
        }
        else
        {
		 	cur=(struct Node*)(cur->Next);
	 	}
	 }
}

int max(int a,int b)
{
   return a<b?b:a;
}
int min(int a,int b)
{
   return a<b?a:b;
}
int getoverrange(int a1,int a2,int b1,int b2)
{
   int start=min(a1,a2)<min(b1,b2)?min(b1,b2):min(a1,a2);
   int end=max(a1,a2)<max(b1,b2)?max(a1,a2):max(b1,b2);
   int range=end-start+1;
   return range>0?range:0;
}


int GetMaxOverRange(struct List* list,int a,int b)
{
    int curmax=0;
    struct Node* cur;
    cur=list->Header;
    while(cur!=NULL)
    {
        int overrange=getoverrange(a,b,cur->Begin,cur->End) ;
        curmax=overrange<curmax?curmax:overrange;

        cur=cur->Next;
    }
    return curmax;
}

void PrintList(struct List* list)
{
    struct Node* tmp;
    tmp=list->Header;
    while(tmp!=NULL)
    {
        printf("line:%d,start:%d,end:%d,len:%d\n",tmp->LineNum,tmp->Begin,tmp->End,tmp->Len);
        tmp=tmp->Next;
    }
}
int GetLen(struct List* list)
{
 	return list->Len;
}

 

 

  main.c

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<unistd.h>
#include"l2lib.h"
#include<fcntl.h>
#define INPUT "2.input.txt" 
#define BUFSIZE 512
int curmax=0;
char buf[BUFSIZE];//read IO buf
char keepbuf[BUFSIZE*2];//handler buf; keep the string don't meet '\n'
int  keeplen=0; //暂存为处理的字符长度
char record[40];//单行支持的最大程度
int curline=0; //当前处理的行号，不包含空格
//hasttable ht;
struct List* list;  //保存暂时不能处理的行

int formatline(int* a,int* b,const char* str)
{
     int ret = sscanf(str,"%d %d",a,b);
}

int Handler(int a,int b)
{

    curline++;
    if(b-a<curmax)
       return curmax;
    else
    {
       curmax = GetMaxOverRange(list,a,b);
       AddList(list,curline,a,b);
       PrintList(list);
       FilterList(list,curmax);
       printf("after filter %d\n",curmax);
        PrintList(list);
       //add to ht;
       //update curmax by item in ht
       //after update, then delete the item in dt
       //that arrange less than new curmax; to lowest memory
    }
}

void HanlderRecord(char* record)
{
     printf("Handler record:%s\n",record);
     int a,b;
     a=b=0;
     formatline(&a,&b,record);
     Handler(a,b);
}

void HandlerBuf(char arr[],int len)
{
     //cory arr to keepbuf
     int i,j;
     for(i=0;i<len;i++)
     {
             keepbuf[keeplen+i]=arr[i];
     }
     keeplen = keeplen + len;
     keepbuf[keeplen]='\0';
     int sindex=0;
     for(i=0;i<BUFSIZE*2&&i<keeplen;i++)
     {
             if('\n' == keepbuf[i])
             {
                   for(j=sindex;j<i;j++)//
                   {
                           record[j-sindex]=keepbuf[j];
                   }
                   record[i-sindex]='\0';
                   HanlderRecord(record);
                   sindex = i + 1;
             }
     }
     if(sindex>0&&keepbuf[keeplen-1]!='\n')
     {
          for(i=sindex,j=0;i<keeplen;i++,j++)
             keepbuf[j]=keepbuf[i];
          keeplen = keeplen - 1 - sindex + 1;
          keepbuf[keeplen]='\0';
     }
     else if(sindex==keeplen)//endwith \0
     {
         keeplen=0;
         keepbuf[keeplen]='\0';
     }
}



int main()
{
    memset(buf,'\0',BUFSIZE);
    memset(keepbuf,'\0',BUFSIZE*2);
    memset(record,'\0',40);
    list=(struct List*)malloc(sizeof(struct List));
    //char mystr1[BUFSIZE]="40 50 \n30 80\n40";
//    char mystr2[BUFSIZE]=" 90 \n10 80\n";
//    HandlerBuf(mystr1,strlen(mystr1));
//    HandlerBuf(mystr2,strlen(mystr2));
    int fd = open(INPUT,O_RDONLY);
    if(fd<0)
    {
            perror("open");
            exit(1);
    }
    int end=0;//0 means no file's end
    int rsize=0;
    while(0 == end)
    {
            rsize = read(fd,buf,BUFSIZE);
            if(rsize>0)
            {
                HandlerBuf(buf,rsize);
            }
            else if(0 == rsize)
            {
                 printf("Read File Done\n");
                 end = 1;
            }
            else
            {
                printf("Read Error\n");
                exit(1);
            }

    }
    printf("max range:%d\n",curmax);
    PrintList(list);
 	free(list);
    //HandlerBuf(keepbuf,keeplen);
    getchar();

}