首页 > 试题广场 >

小美的数对合并

[编程题]小美的数对合并

由于小美对图论十分感兴趣，因此小美希望创建一个属于自己的无向图。他有一个长度为 $n$ 的数组 $a$ ，他认为一对数字 $i, j$ 是好的当且仅当：

$\bullet\ i, j\ (1 \leq i < j \leq n)$ 同时 $i-j < a_i - a_j$ 。

小美创建图的方式则是：对于任意一个点对 $u, v\ (1 \leq u, v \leq n)$ ，如果 $u,v$ 是一对好的数字，则他会在 $u,v$ 之间连上一条无向边。

现在小美想知道，他所创建出的图有多少个极大连通块。由于图中的边数过多他数不过来，因此他想请你帮他算一算。

$\hspace{15pt}$ 对于图上的两个点，如果它们之间有边相连，则称他们位于同一个连通块里。对于一个连通块，如果其已经无法再加入更多的点，则称其为极大连通块。

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个整数 ，表示数组 a 的长度。
第二行输入 n 个正整数 ，表示数组。

除此之外，保证单个测试文件的  之和不超过 。

对于每组测试数据：
输出一行一个正整数表示他的图中连通块的个数。

示例1

输入

2
5

算法知识视频讲解

Python 3

geniecyy

也就是某个bi，前面没有比它更小的，后面没有比它更大的就不会被合并，别的都被合并了

发表于 2025-09-11 17:41:25 回复(0)

提交观点

数组前缀和美团图

难度：

1条回答 8收藏 649浏览

小美的数对合并

扫一扫，把题目装进口袋