题解 | 小红的二分图构造

from math import inf

def solved():
    n = int(input())
    degree = [0] + list(map(int, input().split()))

    k = sum(degree)
    if k % 2== 1:
        print(-1)
        return 
    k //= 2
    dp = [[-inf for _ in range(k+1)] for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(1, n+1):
        for j in range(1, k+1):
            dp[i][j] = dp[i-1][j]
            if j >= degree[i]:
                dp[i][j] = max(dp[i][j], dp[i-1][j-degree[i]]+1)
    if dp[-1][-1] <= 0:
        print(-1)
        return 
    ni, nj = n, k
    v1, v2 = [], []
    while ni > 0:
        if dp[ni][nj] == dp[ni-1][nj]:
            v2.append(ni)
        else:
            v1.append(ni)
            nj -= degree[ni]
        ni -= 1
    print(k)
    i, j = 0, 0
    while i < len(v1) and j < len(v2):
        print(f"{v1[i]} {v2[j]}")
        degree[v1[i]] -= 1
        degree[v2[j]] -= 1
        if degree[v1[i]] == 0:
            i += 1
        if degree[v2[j]] == 0:
            j += 1
    
                    
            

if __name__ == "__main__":
    solved()