UC知道这是一道2005年百度之星的题目~不会做~高手请进~用C语言
来源：百度知道 编辑：UC知道 时间：2024/05/28 14:52:15
题目描述：请编写程序，找出下面 “ 输入数据及格式 ” 中所描述的输入数据文件中最大重叠区间的大小。
对一个正整数 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 ，程序的执行时间越快越好。
感谢二楼的回答~~我很满意这个答案
对一个正整数 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 ，程序的执行时间越快越好。
感谢二楼的回答~~我很满意这个答案
我把程序修改了一下，采用动态分配内存的方法取代直接开辟数组的方法。现在它支持1~1000000行的文件了。
我程序的时间复杂度是O(n^2)，应该有高手可以写出O(n*log(n))的程序。但是，时间复杂度的降低可能会导致空间复杂度过大，有内存占用超出要求的可能。所以我觉得这个程序要好一些。
注意，本程序不检查input文件中数据的合法性！
#include<stdio.h>
#include<stdlib.h>
#define N 1000000
unsigned long fun(unsigned long a0, unsigned long b0, unsigned long a1, unsigned long b1)
{
unsigned long ret=0,temp;
if(a0>b0)
{temp=a0;a0=b0;b0=temp;}
if(a1>b1)
{temp=a1;a1=b1;b1=temp;}
temp=b0<b1?b0:b1;
if(a0<=a1 && b0>=a1)
ret=temp-a1+1;
else if(a1<=a0 && b1>=a0)
ret=temp-a0+1;
return ret;
}
void main()
{
FILE *fp;
unsigned long *s;
unsigned long a,b,n,i,j,max,temp;
if((fp=fopen("\\input.txt","r"))==NULL)
{
printf("Cannot open the file!\n");
exit(0);
}
s=(unsigned long *)malloc(