信息學國家集訓隊作業(yè)wedding

1、WEDDING題目大意：Slavko 在為 Mirko 籌備一個婚禮。在婚禮中的一個重要的活動項目是一個被稱為“Train”的舞蹈。所有的客人排成一列，除了排頭的每一個人都把手搭面一個人的肩上，然后一起跳舞。Slavko 想他的“Train”更加好看。如果相鄰的兩個人的身高差別太大的話，就會顯得不美了。Mirko 的家庭是很守舊的，較小的成員是不能夠排在較大成員的前方的。不是成員的客人是可以排在任意位置的。給你所有客人（包括成員）的身高，還有成員的大小排列。寫一個程序，安排所有客人在 Train 中的位置，使得相鄰兩個人的身高差的絕對值之和最小。輸入格式：輸入文件的第一行是兩個整數(shù)：N 和 K

2、（1=N=10000，1=K=1000，K=N），分別表示客人和成員的人數(shù)。接下來的 N 行每行有一個整數(shù) V（1000=V=2200），表示每個客人的身高?？腿藦?1到 N，其中前K 個標號的客人是成員，并且按照的降序排列。輸出格式：一行一個整數(shù)，表示最小的身高差之和。解題思路：由于的 TRAIN 中在由成員之間的相對位置已經(jīng)確定，所以的任務就是向這個由成員所組成那些非成員的客人。成員所組成的原始 TRAIN 已經(jīng)存在一個“高度差”，而發(fā)現(xiàn)當向相鄰兩個成員之間一個高度介于他們之間的客人的時候，這個“高度差”不會改變。也就是說，存在這樣一個策略，可以將高度介于成員的最大高度與最小高度之間的所有

3、客人全部到TRAIN 中，且使 TRAIN 的身高差之和不變。（對于每個非成員的客人，找到一個相鄰高度“包含”他的點）現(xiàn)在例，感覺告訴在于如何安排超族成員身高范圍的客人拿超出最高高度的客人為，應該盡量將他們安排在一起，因為這樣才能使 TRAIN 中重復的“突起”盡量少。事實證明也是如此?？紤]身高最高的那個客人，顯然將它安排在成員中最高成員的旁邊，或者安排在開頭結尾的時候，會增加最小的高度差。接下來又變成了熟悉的了，因為已經(jīng)沒有客人超出范圍，所以整個算法，如果只求這個最小差值，那么只要又可以采用先前的策略。一下最大最小值即可，復雜度為 O(N)。如果還要輸出隊列的順序，那么可以對所有客人的高度排

4、一下序，然后用 O(N)的掃描完成，總的復雜度是 O(NlogN)。參考程序：program wedding; constinfile=wedding.in;outfile=wedding.out;varn,k,tot:long; d:array1.10000 of long;procedure readdata; varf:text;c1:eger; beginassign(f,infile); reset(f); read(f,n,k);for c1:=1 to n do read(f,dc1); close(f);end;function mini(o1,o2:long) : long; beginif o1max then max:=dc1;if dc1gmax then gmax:=dc1;if dc1max then begin e1:=(gmax-max)*2; e2:=abs(dk-gmax);e3:=abs(d1-gmax); tot:=tot+mini(mini(e1,e2),e3);end;if gmhen begine1:=(min-gmin)*2; e2:=abs(dk-gmin);e3:=abs(d1-gmin); tot:=tot+mini(mini(e1,e2),e3);end; as