Ad—宣传栏清理问题.pptVIP

Ad—宣传栏清理问题 2009.04.24 问题描述 宣传栏清理问题 在学校的学生公寓楼内，每栋楼大厅内的宣传栏上每天都有大量的海报。 为了使用一种特殊的方法清理宣传栏而不留下难看的痕迹，事先需要知道宣传栏上张贴 海报的位置信息。 问题描述 为了简化问题我们规定： 1. 宣传栏用一个区间[0, 1000000]来表示。 2. 假设海报的高度均与宣传栏的高度相同，各海报用两个整数left 和right（rightleft）来表示，表示海报占据区间[left，right]。 3. 两张海报是可以部分或者全部重叠的。 4. 所有海报都不会超过宣传栏的大小。 根据给定的每张海报所占据的区间，请你计算出在宣传栏上所有贴有海报的连续区间。 输入输出范例 输入示例 输出示例 input.txt output.txt 3 (3N50000) 1 8 1 5 9 20 2 8 9 20 对问题的理解和分析 这道题目很军团问题很相似，算法也是基本一样的。 首先先用合并排序法将海报按左区间由小到大排序。之后再求解出连续的区间。 算法与数据结构的选取 首先定义一长度为50000的结构体数组a[n]，将n个左右区的数据a[n].left和a[n].right存入。 用组合排序法将结构体数组由小到大排序。 判断区间是否连续： 如果a[n].left比a[n-1].right小，说明连续。把连续区间扩张。 如果a[n].left比a[n-1].right大，则输出前一组左右区间的数据。 举个例子~~~ 经过合并排序（按left排序） 0 4 1 3 2 6 7 9 8 11 9 14 10 13 Input 7 0 4 7 9 10 13 1 3 8 11 2 6 9 14 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 广告展板 核心代码 merge_sort(arr,n); //调用函数进行合并排序； for(i=1;in;i++) //判断连续区间； { if(arr[i].a=arr[i-1].b) //如果连续，区间扩张； { arr[i].a=arr[i-1].a; if(arr[i].barr[i-1].b) arr[i].b=arr[i-1].b; } else //如果不连续，输出前一个连续区间； printf(%d %d\n,arr[i-1].a,arr[i-1].b); } printf(%d %d\n,arr[n-1].a ,arr[n-1].b); //输出最后一个连续区间； 算法复杂度分析 时间复杂度 O(nlogn+n) 空间复杂度 O（n） 算法的优缺点分析和改进 算法优缺点分析： 优点：用合并排序时间复杂度较低。 缺点：用自然合并排序排序貌似会更快，只是还没弄懂。 Thank You!