小Y与多米诺骨牌

发布时间: 2018年4月15日 22:56   最后更新: 2018年4月15日 23:25   时间限制: 2000ms   内存限制: 128M

小Y 用一副高度不一的多米诺骨牌摆成了一排直线,一共$N$张骨牌,其中第$i$张骨牌在直线上的坐标为$X_i$,高度为$Y_i$,任意两张骨牌的$X$坐标都不相同。摆完之后他发现,推倒一张骨牌并不一定能够让所有牌都连续倒下,于是他想知道最少要直接推倒多少张牌(向左向右皆可),才能让所有牌直接或间接被推倒。

骨牌的厚度不计,也就是说,比如向右($X$ 轴正方向)推倒骨牌$i$ 时,则当骨牌$j$ 满足$X_i < X_j < X_i + Y_i$ 时会被间接地向右推倒(同理,向左时需要满足$X_i \le Y_i < X_j < X_i$)。

多组数据,第一行一个整数$T$($T \le 20$) 表示数据组数。
接着有$T$组数据,每组数据第一行有一个整数$N$($N \le 10^5$) 表示骨牌数量,
之后$N$行每行有两个整数$X_i$; $Y_i$ 表示骨牌的X 坐标和高度(1 \le X_i; Y_i \le 10^9),给出的坐标按顺序严格递增。

对于每组数据,在一行中输出一个整数,表示最少需要直接推倒的骨牌数量。

复制
2
3
1 3
4 2
5 2
3
1 3
4 3
7 7
2
1

第一组样例,需要推倒第一个骨牌,然后向右推倒第二个骨牌即可。第二组样例,向左推倒第三个骨牌即可。

2018

埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛