洛谷P1496 火烧赤壁 （模拟/离散化+差分）

分析可知：将起点和终点按照从小到大的顺序排序，对答案不会产生影响

所以此时我们得到一种模拟做法：

 1 #include
 2 using namespace std;
 3 const int N=2e4+10;
 4 int n,a[N],b[N],ans;
 5 //模拟做法 
 6 int main(){
 7     scanf("%d",&n);
 8     for(int i=1;i<=n;i++)
 9         scanf("%d%d",&a[i],&b[i]);
10     sort(a+1,a+n+1);sort(b+1,b+n+1);
11     for(int i=1;i<=n;i++){
12         ans+=b[i]-a[i];
13         if(i!=n)//不是最后一条线段 
14             if(b[i]>a[i+1]) ans-=b[i]-a[i+1];//减去重复的 
15     }
16     cout<<ans;
17 }

注意可能会有重复的，要减去。

当然，我们还可以离散化（虽然说没有必要）：

 1 #include
 2 using namespace std;
 3 const int N=2e4+10;
 4 int n,ans,temp,cnt,a[N],b[N],x[2*N];
 5 int f[2*N];//判断是否有效
 6 //离散化 
 7 int main(){
 8     scanf("%d",&n);
 9     for(int i=1;i<=n;i++){
10         scanf("%d%d",&a[i],&b[i]);
11         x[++cnt]=a[i];x[++cnt]=b[i];
12     }
13     sort(x+1,x+cnt+1);
14     cnt=unique(x+1,x+cnt+1)-x-1;
15     for(int i=1;i<=n;i++){
16         a[i]=lower_bound(x+1,x+cnt+1,a[i])-x;
17         b[i]=lower_bound(x+1,x+cnt+1,b[i])-x;
18         f[a[i]]++;f[b[i]]--;//差分小优化 
19     }
20     for(int i=1;i<=cnt;i++){
21         temp+=f[i];
22         if(temp) ans+=x[i+1]-x[i];//累加答案 
23     }
24     cout<<ans;
25 } 

什么是有效？比如：

有两对线段（x1,y1）(x2,y2) 如果x1>y2或x2>y1，那么（y2,x1）段或（y1,x2）段无用

因为排序后对答案没有影响，所以这种方法是正确的。