11220: 【原1220】道路监测

题目

题目描述

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

Description

四川省地质灾害多发，地质攻城狮 lostleaf 最近接到了一个建立监测点，监测公路周围山体塌方情况的任务。

公路上共有 \( n \) 个塌方易发点。为了方便起见，可以把公路看作一条数轴，每个塌方易发点的坐标为 \( p_i \)。由于每个塌方易发点的地质情况、重要程度等都有所不同，因此可监测范围也不同。对于第 \( i \) 个塌方易发点，lostleaf 需要保证有一个监测点被建立在 \( r_i \) 范围内(存在一个检测点坐标为 \( x \), ( \( |x-p_i|\leq r_i \) )。

由于经费有限，lostleaf 希望建立最少的监测点来保证所有的塌方易发点都被监测到。

Input Format

第一行一个数, \( n \)

接下来每行两个数 \( p_i \) 和 \( r_i \)

Output Format

一个数，最少需要建立的监测点数目

Sample Input

    3
    1 2 
    2 4 
    10 1

Sample Output

2

Limits

对于80%的数据, \( n\leq 1000 \)

对于100%的数据， \( n\leq 100~000 \)

\( p_i, r_i\leq 100~000~000 \)

yyong119's solution

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

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

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

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i].x >> a[i].l;
    sort(a, a + n, cmp);
    cur_p = a[0].x + a[0].l;
    cnt = 1;
    for (int i = 1; i < n; ++i)
        if (a[i].x - a[i].l > cur_p) {
            cur_p = a[i].x + a[i].l;
            ++cnt;
        }
    cout << cnt << endl;
    return 0;
}