【Sequence】

【问题描述】

给出n个数。请找出一个排列使得相邻两个数的差的绝对值的和最大。

请求出这个最大值。

【输入格式】

第一行一个整数T代表数据组数。

接下来T行,每行一个整数n表示数组大小,紧接着再给出n个整数值。

【输出格式】

对应T组数据输出T行,第i行格式如下:
Case : Si

其中Si表示答案。

输出格式见样例。

【输入样例】

3

4 4 2 15

4 1 1 1 1

2 10 1

【输出样例】

Case 1: 10
Case 2: 0
Case 3: 9

【样例说明】

Case 1:4 1 5 2

Case 2:1 1 1 1

Case 3:10 1

【数据范围】

对100%的输入数据:T≤100 n≤50 数的值不超过1000.

题解的神奇方法:

最优解一定存在于一下两种情况之中(也就是可能有其他排列也是最优,但这两个中一定存在最优)

I 最大的放中间,最小的放左边,次小的放右边,次大的放左边,次次大的放右边……

II 最小的放中间,最大的放左边,次大的放右边,次小的放左边,次次小的放右边……

打个表规律大概就找出来了。

没看出来的我真是哭晕在厕所,以后考试一定要学会利用对拍找规律!

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*