centence

　试题编号：0611

D模拟101-2:：病句

难度级别：B；运行时间限制：1000ms；运行空间限制：256000KB；代码长度限制：2000000B

试题描述

为了提高文章质量，每一篇文章（假设全部都是英文）都会有m名编辑审核，每个编辑独立工作，会把觉得有问题的句子通过下标记录下来，比如［1，10］，1表示病句的第一个字符，10表示病句的最后一个字符。也就是从1到10个字符组成的句子，是有问题的。

现在需要把多名编辑有问题的句子合并起来，送给总编辑进行最终的审核。比如编辑a指出的病句是［1，10］，［32，45］；b编辑指出的病句是［5，16］，［78，94］，那么［1，10］和［5，16］是有交叉的，可以合并成［1，16］，［32，45］，［78，94］。

输入

编辑数量m，之后每行是每个编辑的标记的下标集合，第一个和最后一个下标用英文逗号分隔，每组下标之间用分号分隔。

输出

合并后的下标集合，第一个和最后一个下标用英文逗号分隔，每组下标之间用分号分隔。返回结果是从小到大的递增排列。

输入示例

3
1,10;32,45
78,94;5,16
80,100;200,220;16,32

输出示例

1,45;78,100;200,220

其他说明

对于100%的数据，1<=M<=1e3，句子下标不超过int范围，每个编辑记录的下标不超过1000组。

这道题是昨天本蒟蒻考试的一道题，考试的时候没想到贪心，用模拟骗了20分。

思路：这道题是一道典型的贪心，求区间重复。不过读入有些麻烦，然后根据左端点的大小进行排序。最后设左端点和右端点。如果新的左端点比右端点小，就说明可以合并，求这两个区间的右端点哪个大，用大的更新右端点。如果新的左端点比老的右端点大，就输出老的左端点和右端点，然后把左端点和右端点更新。然后上参考代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,len,b[1000005],e[1000005];
 4 void qsort(int x,int y)//快速排序，根据左端点的大小排序 
 5 {
 6     int i,j,temp;
 7     if(x>y) return;
 8     temp=b[x];
 9     i=x;
10     j=y;
11     while(i!=j)
12     {
13         while(b[j]>=temp&&i<j) j--;
14         while(b[i]<=temp&&i<j) i++;
15         if(i<j) 
16         {
17             swap(e[i],e[j]);
18             swap(b[i],b[j]);
19         }
20     }
21     swap(e[x],e[i]);
22     swap(b[x],b[i]);
23     qsort(x,i-1);
24     qsort(i+1,y);
25 }
26 void solve()//判断是否重合 
27 {
28     int t=e[1],r=b[1];//第一个左端点和右端点就是第一个区间的左端点和右端点 
29     for(int i=2;i<=len;i++)//从第二各区间开始合并 
30     {
31         if(b[i]<=t) t=max(t,e[i]);//如果新的左端点比原来的右端点小，就说明可以合并，并更新右端点 
32         else if(b[i]>t)//如果不能合并，就输出，更新左端点和右端点 
33         {
34             printf("%d,%d;",r,t);
35             t=e[i];
36             r=b[i];
37         }
38     }
39     printf("%d,%d",r,t);//最后一组左端点和右端点肯定输出不了，单独输出。 
40 }
41 int main()
42 {
43     //freopen("centence.in","r",stdin);
44     //freopen("centence.out","w",stdout);
45     scanf("%d",&n);//有n个编辑 
46     for(int i=1;i<=n;i++)
47     {
48         char ch;
49         int s1,e1;
50         while(scanf("%d,%d",&s1,&e1))//要用scanf读入，不然会超时。分号有毒，不用读入 
51         {    
52             b[len+1]=s1;
53             e[len+1]=e1;
54             len++;
55             if(cin.get()=='
') break;
56         }
57     }
58     qsort(1,len);//排序 
59     solve();//输出 
60     return 0;//完美结束 
61 }