上例线太多太复杂，用简单点的图来说明吧！

已知k[]={0, 2,0,1,0}，求C[]。（正确答案是={0, 3,1,4,2}）。上面的做法是L.Insert(0,4/1,3/0,2/2,1)。L的0,1...n-1位，对应布线终点的1,2...n位，以下解释/证明上面的做法（每引入一条线w，就增加k[w]个交点）！

数学归纳法：起点序列按从大到小插入L。则插入第一点(即起点4)时只有一条线(4--1),显然成立(k[4]=0)。插入第二点(3)后有两条线，对应的k[3]只有0/1两种情况，不难验证这两种情况都成立。所以令插入i=w-1点后（不妨以图c)为例）成立：即“起点序列”{S[1],S[2]...S[j],S[j+1]...S[w-1]=2,4,3}满足{k[1],k[2]...k[j],k[j+1]...k[w-1]=0,1,0}。当插入i= w点后（不妨以图d)为例），即在w-1条线中再加一条线(1--3)：{S[1],S[2]...S[j],S[w],S[j+1]...S[w-1]=2,4,1,3}（对应的终点满足：C[w](3)-C[1](1)=k[w](2)）。忽略S[w]线，其终点右侧的{S[j+1]...S[m]}={3}部分终点统统右移一位(从“3”变为“4”)；其终点左侧的{S[1]...S[j]}={2,4}部分的终点不变（仍为“1,2”），再加上每条线的起点i显然不变，所以二者整体的k[i]不变（k[i]的计算条件只看大小关系，关键），K当然也不变。加入S[w]后，由于其起点是最左/小点，所以所有终点小于C[w]的线都与它有交点，而大于C[w]的线都没有，因此新增的交点数为C[w]-C[1]=k[w]。证毕！

当然这样得出的是“起点序列”S[i]，要得到“终点序列”C[i]还要做简单的处理（对称变换，交点集显然不变）。
--
修改:warsong FROM 221.237.150.*
FROM 221.237.150.*