所有对象都可以按顺序配对吗？

Question

首先,这不是一个家庭作业或类似的东西,这是我在上一个问题候选人找到数组中的多数元素时的一个暗示性问题.

有n 各种对象O ₁,O ₂,...,O _n,并且有一个数组F[1...n],F[i]是Oi的数量(即有F[i]O _i s,F[1...n]给出数组),以及每个F[i]> 0.

现在使用以下规则来配对对象:

如果i != j,_我可以与O _j配对,
否则,如果i == j,_我不能与O _j配对.

即,只有两种不同的物体可以相互配对.

1. 输入数组F[1...n]是否存在有效的配对方法？给出一个具有最佳时间复杂度的算法来判断真或假,并证明其正确性.

2. 如果存在,则输出一个有效的配对序列.给出算法和时间/空间复杂度分析.

例如, 输入 F[] = {10, 2, 4, 4};

然后至少存在一种有效的配对方法:

2 O ₁ s和2 O ₂ s配对,4 O ₁ s和4 O ₃ s配对,4 O ₁ s和4 O ₄ s配对.

一个有效的配对序列是:

(1,2)(1,2)(1,3)(1,3)(1,3)(1,3)(1,4)(1,4)(1,4)(1,4)

Answer 1

检查O(n)中是否存在解决方案

让我们s的总和F.

• 如果s是奇怪的话没有解决方案(直观)
• 如果存在一个i,使得F[i] > s/2没有溶液(直观的)
• 否则,存在一个解决方案(按结构证明)

在O(n)中寻找解决方案

# Find s
s = 0
for i in 1..n:
    s += F[i]

# Find m such that F[m] is maximal
m = 1
for i in 1..n:
    if F[i] > F[m]:
         m = i

if s % 2 != 0 or F[m] > s/2:
    fail

a = 1
b = 1

# Pair off arbitrary objects (except those of type m) until F[m] = s/2    
while s/2 > F[m]:
    # Find a type with a non-zero frequency
    until F[a] > 0 and a != m:
        a = a + 1
    # Find another type with a non-zero frequency
    until F[b] > 0 and b != m and b != a:
        b = b + 1

    count = min(F[a], F[b], s/2 - F[m])
    pair(a, b, count)

# Pair off objects of type m with objects of different types
while F[m] > 0:
    # Find a type with a non-zero frequency
    until F[a] > 0 and a != m:
        a = a + 1
    pair(a, m, F[a])

end of algorithm

def pair(a, b, count):
    # Pairs off 'count' pairs of types a and b
    F[a] = F[a] - count
    F[b] = F[b] - count
    s = s - (2 * count)
    output "Pairing off $a and $b ($count times)"

这两个while循环都是线性的.第一个while循环在每次迭代时递增a或递增b至少一次,因为匹配后count对或者F[a]为零,或者F[b]为零,或者s/2 = F[m]循环终止.a并且b可以在n访问所有元素之前每次增加最多次数.第二个while循环也是线性的,因为它a在每次迭代期间至少增加一个.

关键不变量是
(1) F[m]是F
(2)中 最大的元素F[m] <= s/2
我认为两者在检查时都相当明显.

使用内循环,只要s/2 > F[m]必须至少有两个其他具有非零频率的对象类型.如果只有一个,a那么
F[a] + F[m] = s
F[a] = s - F[m] > s - s/2(从循环条件)
F[a] > s/2
F[a] > F[m]
,这是一个不变量(1)的矛盾.

由于存在至少两种具有非零频率的类型(此外m),循环将能够找到类型a并且b将对象关闭直到s/2 = F[m].

第二个循环是微不足道的.由于正好一半的对象是类型的m,因此每个类型m的对象可以与不同类型的对象配对.