Skip to content

11025: 【原1025】水枪灭火

题目

题目描述

author: 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1025

Description

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

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

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

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

Input Format

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

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

\( -10^{9} \leq Ai , Bi \leq 10^{9} \)

\( N \leq 20000 \)

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

Output Format

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

Sample Input

3
-1 1
5 11
2 9

Sample Output

11

FineArtz's solution 

/* 水枪灭火 */
#include <iostream>
#include <algorithm>
using namespace std;

class Interval{
public:
    //constructor
    Interval() : l(0), r(0) {}
    Interval(int x, int y) : l(x), r(y) {}
    Interval(const Interval &i) : l(i.l), r(i.r) {}

    int l, r;
};
inline bool cmp(Interval i1, Interval i2){
    return (i1.l < i2.l || i1.l == i2.l && i1.r > i2.r);
}

int main(){
    int n;
    cin >> n;
    Interval a[20005];
    for (int i = 0; i < n; ++i)
        cin >> a[i].l >> a[i].r;
    sort(a, a + n, cmp);
    /*for (int i = 0; i < n; ++i)
        cout << a[i].l << ' ' << a[i].r << endl;*/
    long long nowl = a[0].l, nowr = a[0].r;
    long long ans = 0;
    for (int i = 1; i < n; ++i){
        if (nowl <= a[i].l && a[i].l <= nowr){
            if (nowr < a[i].r) nowr = a[i].r;
        }
        else{
            ans += nowr - nowl;
            nowl = a[i].l;
            nowr = a[i].r;
        }
    }
    ans += nowr - nowl;
    cout << ans << endl;
    return 0;
}

ligongzzz's solution 

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<pair<int, int>> val_data(n);

    for (int i = 0; i < n; ++i) {
        cin >> val_data[i].first >> val_data[i].second;
    }

    sort(val_data.begin(), val_data.end(), [](pair<int, int>& a, pair<int, int>& b) {return a.first < b.first; });

    long long ans = 0;
    int cur_start = val_data[0].first, cur_end = val_data[0].second;
    for (auto p : val_data) {
        if (p.first > cur_end) {
            ans += (long long)cur_end - (long long)cur_start;
            cur_start = p.first;
            cur_end = p.second;
        }
        else {
            cur_end = p.second > cur_end ? p.second : cur_end;
        }
    }
    ans += (long long)cur_end - (long long)cur_start;

    cout << ans;

    return 0;
}