信息学国家集训队作业wedding

1、WEDDING题目大意：Slavko 在为 Mirko 筹备一个婚礼。在婚礼中的一个重要的活动项目是一个被称为“Train”的舞蹈。所有的客人排成一列，除了排头的每一个人都把手搭面一个人的肩上，然后一起跳舞。Slavko 想他的“Train”更加好看。如果相邻的两个人的身高差别太大的话，就会显得不美了。Mirko 的家庭是很守旧的，较小的成员是不能够排在较大成员的前方的。不是成员的客人是可以排在任意位置的。给你所有客人（包括成员）的身高，还有成员的大小排列。写一个程序，安排所有客人在 Train 中的位置，使得相邻两个人的身高差的绝对值之和最小。输入格式：输入文件的第一行是两个整数：N 和 K

2、（1=N=10000，1=K=1000，K=N），分别表示客人和成员的人数。接下来的 N 行每行有一个整数 V（1000=V=2200），表示每个客人的身高。客人从 1到 N，其中前K 个标号的客人是成员，并且按照的降序排列。输出格式：一行一个整数，表示最小的身高差之和。解题思路：由于的 TRAIN 中在由成员之间的相对位置已经确定，所以的任务就是向这个由成员所组成那些非成员的客人。成员所组成的原始 TRAIN 已经存在一个“高度差”，而发现当向相邻两个成员之间一个高度介于他们之间的客人的时候，这个“高度差”不会改变。也就是说，存在这样一个策略，可以将高度介于成员的最大高度与最小高度之间的所有

3、客人全部到TRAIN 中，且使 TRAIN 的身高差之和不变。（对于每个非成员的客人，找到一个相邻高度“包含”他的点）现在例，感觉告诉在于如何安排超族成员身高范围的客人拿超出最高高度的客人为，应该尽量将他们安排在一起，因为这样才能使 TRAIN 中重复的“突起”尽量少。事实证明也是如此。考虑身高最高的那个客人，显然将它安排在成员中最高成员的旁边，或者安排在开头结尾的时候，会增加最小的高度差。接下来又变成了熟悉的了，因为已经没有客人超出范围，所以整个算法，如果只求这个最小差值，那么只要又可以采用先前的策略。一下最大最小值即可，复杂度为 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