题解 | 小红的二分图构造

def getHalf(d,s,t):
    now=0
    for i,j in enumerate(s):
        if j==1:
            now+=d[i]
    if now==t//2:
        return s
    elif now>t//2:
        return None
    else:
        if len(s)==len(d):
            return None
        s1=s[:]
        s1.append(1)
        s2=s[:]
        s2.append(2)
        output1=getHalf(d,s1,t)
        if output1==None:
            return getHalf(d,s2,t)
        else:
            return output1

def printOutput(indices,d):
    left=[]
    right=[]
    for i,j in enumerate(indices):
        if j==1:
            left.append(i)
        else:
            right.append(i)
    m=d[left[0]]
    n=d[right[0]]
    while True:
        print("%d %d"%(left[0]+1,right[0]+1))
        m-=1
        n-=1
        if m==0 and len(left)==1:
            break
        if m==0:
            left.pop(0)
            m=d[left[0]]
        if n==0:
            right.pop(0)
            n=d[right[0]]

n=int(input())
d=list(map(int,input().split()))
s=sum(d)
if s % 2 !=0:
    print(-1)
else:
    indices=getHalf(d,[],s)
    if indices==None:
        print(-1)
    else:
        indices=indices+[0]*(len(d)-len(indices))
        print(s//2)
        printOutput(indices,d)

getHalf找到总和为一半的列表索引集，根据索引集输出结果