编程题
### 问题描述 小蓝是一位卫生意识很强的年轻人,他关心吸烟对周围人的影响。一天,他站在一个人群中,这个人群有 $n$ 个人,其中有 $k$ 个人吸烟。每个吸烟者站在不同的位置,他们的位置分别是 $p_1, p_2, p_3, \ldots, p_k$,而且他们的烟的影响半径分别为 $f_1, f_2, f_3, \ldots, f_k$。 小蓝想知道在这个人群中,有多少人不会受到烟的影响。一个人不会受到吸烟的影响,只有当他站在的位置不在任何吸烟者的影响半径内。即第 $i$ 个人吸烟,那么区间 $[i-f_i, i+f_i]$ 的人都会收到影响,其他人不会收到影响。 你能帮助小蓝找出有多少人不会受吸烟的影响吗? ### 输入格式 第一行包含两个整数 $n$ 和 $k$,表示人群中的总人数和吸烟者的数量。 接下来 $k$ 行,每行包含两个整数 $p_i, f_i$,代表第 $i$ 个人的位置和他的影响半径。 ### 输出格式 输出一个整数,表示不会受烟影响的人数。 ### 样例输入 ``` 4 2 1 2 2 1 ``` ### 样例输出 ``` 1 ``` ### 说明 - $1$ 号人影响的区间为 $[1,3]$。 - $2$ 号人影响的区间为 $[1,3]$。 因此 $4$ 号不会受影响。 ### 评测数据范围 $1\le k\le n \le 10^5, 1 \le f_i \le 10^5 $。
查看答案
赣ICP备20007335号-2