Skip to content

11992: 【原1992】绮礼的阴谋

题目

题目描述

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

题目描述

第四次圣杯战争开始了。 为了收集敌人的情报，言峰绮礼命令他的使魔Assassin将自己的灵体分成\(n\)份，分别监视教堂外的长直走道。

Assassin每份灵体的能力不同。 第\(i\)份灵体可以监视到的区域是闭区间\([a_i,b_i]\)。

绮礼想知道，监控范围内的区域的总长度是多少。

比如，第一份灵体的视野是\([-1,1]\)，第二份灵体的视野是\([0,2]\)，第三份灵体的视野是\([3,4]\)。 那么绮礼能获得的全部视野是\([-1,2]\cup[3,4]\)，长度为\(4\)。

输入格式

第\(1\)行有一个整数，表示灵体数量\(n\)。 接下来有\(n\)行，每行两个整数\(a_i\)和\(b_i\)，表示第\(i\)个灵体的视野为\([a_i,b_i]\)。

输出格式

输出一个整数\(s\)，表示获得的全部视野的总长度。

样例输入

3
3959 21659
8666 26551
3392 11450

样例输入

23159

样例解释

\( [3959,21659]\cup[8666,26551]\cup[3392,11450] = [3392,26551] \)

总长度为 \( 26551-3392 = 23159 \)

说明

时间限制：1000ms，内存限制：50000kb。

对于全部数据：灵体数量\(1 \leq n \leq 10000\)。 每份灵体的视野 \(1 \leq a_i ,b_i\leq 2 \times 10^9\)

对于30%数据: 灵体数量\(1 \leq n \leq 50\)。

BugenZhao's solution 

//
// Created by BugenZhao on 2019/3/23.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

using ll=long long;

/*class Interval {
public :
    int l;
    int r;

    bool operator<(const Interval &rhs) const {
        if (l < rhs.l)
            return true;
        if (rhs.l < l)
            return false;
        return r < rhs.r;
    }
};*/

int main() {
    int starts[10005], ends[10005];
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &starts[i], &ends[i]);
    }

    sort(starts, starts + n);
    sort(ends, ends + n);

    int length = 0;
    int i = 0, j = 0;
    for (; i < n; ++i) {
        if (i == n - 1 || starts[i + 1] > ends[i]) {
            length += ends[i] - starts[j];
            j = i + 1;
        }
    }
    cout << length << endl;
    return 0;
}

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[10005];
    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 "cstdio"
using namespace std;

int times[10009][2] = { 0 };

template <class T>
void quick_sort(T start, T end) {
    if (start == end)
        return;
    auto i = start, j = end;
    --j;
    if (i == j)
        return;
    //交换
    auto key = (*start)[0];
    auto tmp = (*start)[1];
    for (bool status = true; i != j;) {
        if (status) {
            if ((*j)[0] < key) {
                (*i)[0] = (*j)[0];
                (*i)[1] = (*j)[1];
                ++i;
                status = false;
            }
            else
                --j;
        }
        else {
            if ((*i)[0] > key) {
                (*j)[0] = (*i)[0];
                (*j)[1] = (*i)[1];
                --j;
                status = true;
            }
            else
                ++i;
        }
    }
    (*i)[1] = tmp;
    (*i)[0] = key;
    //递归
    quick_sort(start, i + 1);
    quick_sort(i + 1, end);
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        scanf("%d %d", &times[i][0], &times[i][1]);
    }
    quick_sort(times, times + n);

    int ans = 0;
    int cur_left = 0, cur_right = 0;
    for (int i = 0; i < n; ++i) {
        if (times[i][0] > cur_right) {
            ans += cur_right - cur_left;
            cur_left = times[i][0];
            cur_right = times[i][1];
        }
        else {
            if (cur_right < times[i][1])
                cur_right = times[i][1];
        }
    }
    ans += cur_right - cur_left;

    cout << ans;

    return 0;
}

skyzh's solution

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

struct Range {
    int L, R;
} R[10000];

bool cmp(const Range& a, const Range& b) {
    return a.L <= b.L;
}

int main() {
    long long SUM = 0;
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> R[i].L >> R[i].R;
    sort(R, R + N, cmp);
    int LS = R[0].L, LE = R[0].R;
    for (int i = 1; i < N; i++) {
        if (R[i].L > LE) {
            SUM += (long long) LE - LS;
            LE = R[i].R;
            LS = R[i].L;
        } else if (R[i].R > LE) {
            LE = R[i].R;
        }
    }
    SUM += (long long) LE - LS;
    cout << SUM << endl;
    return 0;
}

yyong119's solution 

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N 10010
using namespace std;

struct node{
    int l, r;
} a[MAX_N];
int n, cnt;

inline bool cmp(node p, node q) {
    return p.l < q.l;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &a[i].l, &a[i].r);
    sort(a, a + n, cmp);
    int upd = 0, cur_l = a[0].l, cur_r = a[0].r;
    for (int i = 1; i < n; ++i) {
        if (a[i].r <= cur_r) continue;
        if (a[i].l > cur_r) {
            cnt += cur_r - cur_l;
            cur_l = a[i].l;
        }
        cur_r = a[i].r;
    }
    cnt += cur_r - cur_l;
    printf("%d\n", cnt);
    return 0;
}