呼呼~(yú)想了一會(huì)兒呢~還打了草稿
首先,我們假設(shè)p1,p2,.pn中各元素的逆序數(shù)為t1,t2……,tn
即p1的逆序數(shù)是t1（其實(shí)t1=0,為說(shuō)明問(wèn)題方便,把它寫成t1）,p2的逆序數(shù)是t2……pn的逆序數(shù)是tn
另外,由逆序數(shù)的定義,可以知道p1,p2,.pn是互不相同的數(shù)字
為作下一步推理,先解釋一個(gè)結(jié)論,即相鄰兩個(gè)數(shù),交換一次,若前一個(gè)數(shù)比后一個(gè)數(shù)大,則整個(gè)數(shù)列的逆序數(shù)減1,反之加1
即對(duì)數(shù)列a,b→b,a
若a＞b,則逆序數(shù)又1變0,反之由0變1
這樣的話,容易知道,對(duì)于數(shù)列p1,p2,.pn中一元素pn而言,其逆序數(shù)為tn,表明p1,p2,.pn,在p1,p2,.pn-1中比pn大的數(shù)的個(gè)數(shù)為tn個(gè),比pn小的數(shù)的個(gè)數(shù)為n-1-tn個(gè)
那么p1,p2,.pn變換為pn,p1,p2,.pn-1需要經(jīng)過(guò)n-1次相鄰變換,且整體考慮的話,其中有tn次逆序數(shù)減1的變換,有n-1-tn次逆序數(shù)加1的變換,所以pn,p1,p2,.pn-1的逆序數(shù)為k-tn+n-1-tn
同樣的道理,對(duì)于pn-1而言,對(duì)數(shù)列pn,p1,p2,.pn-1而言,在pn,p1,p2,.pn-2中有tn-1個(gè)比之大的數(shù),有n-2個(gè)比之小的數(shù)字,所以pn,p1,p2,.pn-1變換為pn,pn-1,p1,p2,.pn-2,需要經(jīng)歷n-2次變換,且整體考慮的話,要經(jīng)過(guò)tn-1次逆序數(shù)減1的變換,有n-1-tn-1次逆序數(shù)加1的變換,所以pn,pn-1,p1,p2,.pn-2的逆序數(shù)變?yōu)閗-tn+n-1-tn-tn-1+n-2-tn-1
……
以上類推,一直變形到pn,.p2,p1,同理可證其逆序數(shù)=k-tn+n-1-tn-tn-1+n-2-tn-1-tn-2+n-3-tn-2-……-t1+0-t1=k-2(tn+tn-1+……+t1)+n-1+n-2+……+1
由已知條件知道tn+tn-1+……+t1=k
故變形所得的pn,.p2,p1的逆序數(shù)為k-2k+(n-1)n/2=(n-1)n/2-k
經(jīng)過(guò)N多實(shí)例驗(yàn)證,確實(shí)正確無(wú)誤,證明過(guò)程沒(méi)有錯(cuò)誤~