百度之星 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 512int curmax=0;char buf[BUFSIZE];//read IO bufchar 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();}

?

?

?