更准确的说法:加入S[w]后,由于其起点是最左/小点,所以1.以前的w-1条线都不会在
自身右侧与其相交(即k[1]...k[w-1]都不变)。2.所有终点小于C[w]的线都与它在它右
侧有交点,而大于C[w]的线都没有,因此新增的交点数为C[w]-C[1]=k[w]。
【 在 warsong (品雨居士~马小虎) 的大作中提到: 】
: 上例线太多太复杂,用简单点的图来说明吧!
: 已知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[
: ...................
--
FROM 221.237.150.*