翻译
查看原帖
翻译
735330
hloixyh楼主2023/3/9 20:50

题目描述

现在,在一个一维平面中给你 nn 条线段,每条线段由2个整数表示它的两个端点。

我们定义函数 f(x)f(x) 为可以覆盖点 xx 的线段个数(覆盖的条件是一条线段的左端点表示的数 x\le x,右端点表示的数 x\le x )。

如果有一个点 xx 对于其他的所有点都有 f(y)<f(x) f(y) < f(x) (也就是说在所有的点中, 包含点 xx的线段是最多的),我们就把点 xx 称为理想点。

现在给你一个整数 kk ,问你能否删除一些线段(也可以不删除)使点 kk 成为理想点。

输入格式

第一行一个整数 tt ,表示测试数据的组数。

每组数据的第一行有两个整数 nnkk,含义如题。

接下来,有 nn 行,每行两个整数,表示一条线段的两个端点。

输出格式

如果在某一个测试点中,可以通过删除一些线段(也可以不删除)使点 kk 成为理想点则输出YES,否则输出NO

你可以在任何情况下打印每个字母(YESyesYes都将被识别为可以,NOnonO都将被识别为不可以)。

说明/提示

数据范围:

1t10001 \le t \le 1000

1n,k501 \le n, k \le 50

1liri501 \le l_i \le r_i \le 50

样例解释:

在第一组样例中,点 33 已经是理想点了,所以不需要删除线段。

在第四组样例中,删除除 [5,5][5, 5] 以外的所有线段就可以使点 55 成为理想点。

2023/3/9 20:50
加载中...