百度之星 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();}?
?
?