【上海交大oj】水枪灭火（计算区间长度）

1025. 水枪灭火

Description

以此题纪念上海“11•15”高楼火灾遇害者

11月15日下午，上海静安区胶州路728号的一幢28层民宅发生严重火灾。消防部门接警后立刻出动25个消防中队、百余辆消防车投入灭火抢救行动，紧急疏散和救助了附近居民百余人。火灾导致58人遇难。

此时大楼的所有楼层已经全部被烈火包围，每辆消防车的高压水枪可以对连续的若干个楼层进行灭火，把高楼看成竖直的y轴（原点可放在任意位置），若一辆消防车对[10,1000]这段区域灭火，则10到1000这段区域的火就被扑灭了。请求出在所有消防车完成灭火工作后，已经被扑灭的区域的总长度。

高压水枪对于控制火势起着很关键的作用。非常遗憾的是，对于28楼的建筑，上海高压水枪的喷射高度“只能到十楼”。

Input Format

第一行：N （消防车的数目）

以后N行，每行两个数：Ai Bi (表示第i个消防车灭火区域的起始位置和终止位置)

−109≤Ai,Bi≤109

N≤20000

若 Ai=Bi，此段区域就是一个点，看作没有长度。

Output Format

输出被扑灭区域的总长度。

Sample Input

3
-1 1
5 11
2 9

Sample Output

11
=======================================================================
实现方法比较多，总体就是先排序
1. 只对区间左边界排序，排完序后计算长度时对一个点可能要扫描较多的点（右边界较大）；
2. 左右边界都进行排序，然后一一对应形成区间，对一个区间只需判断和下一个区间是否重复即可；
3.这个思想比较巧妙，把左右边界同时排序，然后遍历，统计剩余的左边界数目，同时记录当前最小的左边界，当遇到最大的右边界时（即剩余左边界为零时）计算区间长度，下一个点记为新的左边界。
我用的第三种，在实现时遇到一个小问题导致有一个点没有通过，就是排序的时候，如果有几个相同的数，那么就可能是右边界的数排在了左边，这样就不能保证时刻左边界数量大于右边界了，所以在排序的时候就要考虑相同时把左边界排在左边。下面是代码：

#include <iostream>
#include <algorithm>
using namespace std;

struct onepoint{
    long long coord;  //区间边界值 
    bool dire;          //左边界还是右边界 
};
bool compare(onepoint a,onepoint b) {
    if (a.coord==b.coord && a.dire < b.dire) return 1; //确保左边界排在左边 
    return a.coord<b.coord;
}
int main(){
    int N,i,j;
    
    cin>>N;
    onepoint interval[2*N];
    for (i=0;i<N;++i) {
        cin>>interval[2*i].coord>>interval[2*i+1].coord;
        interval[2*i].dire = 0;
        interval[2*i+1].dire = 1;
    }
    sort(interval,interval+2*N,compare);
    long long length = 0;
    long long left = interval[0].coord;
    long long num_left = 1;
    for (i=1;i<2*N;++i) {
        if (num_left==0) left = interval[i].coord;    //更新最左边界值    
        if (interval[i].dire) num_left--;
        else num_left++;                           //更新左边界数量 
        if (num_left==0) length+=interval[i].coord - left;     //更新长度 
    }
    cout<<length;
    return 0;
}