Skip to content

Latest commit

 

History

History
145 lines (104 loc) · 4.42 KB

1433d.md

File metadata and controls

145 lines (104 loc) · 4.42 KB
Raw

题目地址(D. Districts Connection)

https://codeforces.com/problemset/problem/1433/D

题目描述

There are 𝑛 districts in the town, the 𝑖-th district belongs to the 𝑎𝑖-th bandit gang. Initially, no districts are connected to each other.

You are the mayor of the city and want to build 𝑛−1 two-way roads to connect all districts (two districts can be connected directly or through other connected districts).

If two districts belonging to the same gang are connected directly with a road, this gang will revolt.

You don't want this so your task is to build 𝑛−1 two-way roads in such a way that all districts are reachable from each other (possibly, using intermediate districts) and each pair of directly connected districts belong to different gangs, or determine that it is impossible to build 𝑛−1 roads to satisfy all the conditions.

You have to answer 𝑡 independent test cases.

Input
The first line of the input contains one integer 𝑡 (1≤𝑡≤500) — the number of test cases. Then 𝑡 test cases follow.

The first line of the test case contains one integer 𝑛 (2≤𝑛≤5000) — the number of districts. The second line of the test case contains 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤109), where 𝑎𝑖 is the gang the 𝑖-th district belongs to.

It is guaranteed that the sum of 𝑛 does not exceed 5000 (∑𝑛≤5000).

Output
For each test case, print:

NO on the only line if it is impossible to connect all districts satisfying the conditions from the problem statement.
YES on the first line and 𝑛−1 roads on the next 𝑛−1 lines. Each road should be presented as a pair of integers 𝑥𝑖 and 𝑦𝑖 (1≤𝑥𝑖,𝑦𝑖≤𝑛;𝑥𝑖≠𝑦𝑖), where 𝑥𝑖 and 𝑦𝑖 are two districts the 𝑖-th road connects.
For each road 𝑖, the condition 𝑎[𝑥𝑖]≠𝑎[𝑦𝑖] should be satisfied. Also, all districts should be reachable from each other (possibly, using intermediate districts).

Example
inputCopy
4
5
1 2 2 1 3
3
1 1 1
4
1 1000 101 1000
4
1 2 3 4
outputCopy
YES
1 3
3 5
5 4
1 2
NO
YES
1 2
2 3
3 4
YES
1 2
1 3
1 4

前置知识

  • 构造
  • 图

公司

  • 暂无

思路

需要明确的是除非小镇都属于统一帮派，否则总可以找到一种合法的 connect 方式。这是因为连接一个小镇的数目不限，也就是说你可以有任意个小镇连着某一个小镇。

比如有两个帮派，那么只需 abab 这样连即可。如果 a 还有剩下就全部连到一个 b 上，反之也是类似。如果有多个，那么只需要分治即可。即将一个帮派和 n - 1 个帮派看成两个帮派进行处理。

还有一种思考方法是，对于每一个小镇，我们只要能找到和它不一样的小镇即可（无论它之前是否被其他小镇连接，因此小镇可以被连接任意次），这其实也等价于小镇所属帮派大于 1。

明确了这一点，我们就可以写代码了。具体算法是：对于每一个小镇，我们找到任意一个和它不同帮派的小镇进行连接。

暴力的方法是每次找“任意一个和它不同帮派的小镇” 都线性枚举。时间复杂度为 $O(n^2)$

t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    if max(a) == min(a):
        print("NO")
    else:
        print("YES")
        for j in range(len(a) - 1):
            r = len(a) - 1
            while a[j] == a[r]:
                r -= 1
            print(j + 1, r + 1)

上面说了，只要帮派种类有 2 个就够了，再多也是没有意义的。

因此我们可以将其分为两个门派，一个是和 A[0] 门派一样的 x，一个是和 A[0] 门派不一样的 y。

这样，如果小镇门派等于 A[0] 门派，那么将其连到 y，否则连到 x。

关键点

  • 只要分配两个门派就够了

代码

  • 语言支持：Python3

Python3 Code:

t = int(input())

for _ in range(t):
    n = int(input())
    A = list(map(int, input().split(" ")))
    x = A[0]
    y = -1
    for i in range(1, n):
        if A[i] != A[0]:
            y = i
    if y == -1:
        print("NO")
    else:
        print("YES")
        # either assign x or y
        for i in range(1, n):
            if A[i] == x:
                print(i + 1, y + 1)
            else:
                print(i + 1, 1)

复杂度分析

令 n 为数组长度。

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$