我要招人

去企业版

首页 > 试题广场 >

小美的数对合并

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

热度指数：221 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

由于小美对图论十分感兴趣，因此小美希望创建一个属于自己的无向图。他有一个长度为 $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

算法知识视频讲解

Java

Sen🍓🍀

import java.util.*;

//  i-a[i] < j-a[j], i<j
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t-- > 0) {
            int n = in.nextInt();
            int[] a = new int[n + 1];
            int[] b = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                a[i] = in.nextInt();
                b[i] = i - a[i];
            }

            Deque<Integer> stack = new ArrayDeque<>(); // 单调栈：维护各个连通块最小值
            for (int i = 1; i <= n; i++) {
                int min = b[i];
                while (!stack.isEmpty() && stack.peek() < b[i]) { // 可以合并前面的连通块
                    min = Math.min(min, stack.pop());
                }
                stack.push(min); // 只要连通块最小值<b[i]，就可通过b[i]连边，合并前面的连通块
            }
            System.out.println(stack.size());
        }
    }
}

发表于 2025-10-26 13:09:54 回复(0)

Python 3

geniecyy

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

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

请叫我牛柳

完全不理解，来个大佬解释一下

发表于 2025-08-08 10:57:55 回复(0)

提交观点

问题信息

数组前缀和美团图

难度：

3条回答 8收藏 647浏览

小美的数对合并

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题