数组4.0

[编程题]数组4.0

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

小红有一个长度为 $n$ 的数组 $a$ ，下标从 $1$ 开始。

如果两个数 $a_i,a_j$ 的绝对差值为 $1$ ，那么 $i,j$ 之间存在一条无向边。

为了使得所有索引之间相互可达，小红至少需要手动再加多少条边。

输入描述:

每个测试文件均包含多组测试数。第一行输入一个整数 ,代表数据组数,每组测试数据描述如下：
对于每一组测试数据:

第一行一个整数 ，表示数组长度。

第二行  个整数，第  个数为 ，表示数组元素。

单个测试文件保证 。

输出描述:

输出共  行，每行一个整数，表示一个整数，表示至少需要手动再加多少条边才是使得图联通。

示例1

输入

输出

0
1

算法知识视频讲解

Z_L_G

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;

void solve() {
  int n;
  cin >> n;
  vector<ll> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a.begin() + 1, a.end());

  int cnt = 0;
  for (int i = 1; i <= n;) {
    int j;
    for (j = i; j + 1 <= n && (a[j] == a[j + 1] || a[j + 1] == a[j] + 1); j++)
      ;
    if (a[i] == a[j]) {
      cnt += j - i + 1;
    } else {
      cnt += 1;
    }
    i = j + 1;
  }
  cout << cnt - 1 << endl;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

发表于今天 11:50:31 回复(0)