A - Difference Row

2023-12-28 08:32

文章标签 row difference

本文主要是介绍A - Difference Row，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

You want to arrange n integers a1, a2, ..., an in some order in a row. Let's define the value of an arrangement as the sum of differences between all pairs of adjacent integers.

More formally, let's denote some arrangement as a sequence of integers x1, x2, ..., xn, where sequence x is a permutation of sequencea. The value of such an arrangement is (x1 - x2) + (x2 - x3) + ... + (xn - 1 - xn).

Find the largest possible value of an arrangement. Then, output the lexicographically smallest sequence x that corresponds to an arrangement of the largest possible value.

Input

The first line of the input contains integer n (2 ≤ n ≤ 100). The second line contains n space-separated integers a1, a2, ..., an(|ai| ≤ 1000).

Output

Print the required sequence x1, x2, ..., xn. Sequence x should be the lexicographically smallest permutation of a that corresponds to an arrangement of the largest possible value.

Input

5
100 -100 50 0 -50

Output

100 -50 0 50 -100

Hint:

In the sample test case, the value of the output arrangement is (100 - ( - 50)) + (( - 50) - 0) + (0 - 50) + (50 - ( - 100)) = 200. No other arrangement has a larger value, and among all arrangements with the value of 200, the output arrangement is the lexicographically smallest one.

Sequence x₁, x₂, ... , x_p is lexicographically smaller than sequence y₁, y₂, ... , y_p if there exists an integer r(0 ≤ r < p) such that x₁ = y₁, x₂ = y₂, ... , x_r = y_r and x_r + 1 < y_r + 1.

题意描述：

给你n个数，然后求字典序最小，排完序之后，求两两相邻元素差和最大的序列。

解题思路：

根据所给的公式可知，中间元素被抵消，所以只需a1-an最大即可，所以先整体从小到大排列，然后将最后一个与第一个元素互换位置。

解题细节：

运用sort排序，先输出a[n-1],最后输出a[0].

代码：

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{int a[101];int n;while(cin>>n){int i;for(int i=0;i<n;i++)cin>>a[i];sort(a,a+n);cout<<a[n-1]<<' ';for(i=1;i<n-1;i++){cout<<a[i]<<' ';}cout<<a[0]<<endl;}return 0;
}

思路：

做题数量还不够，一开始未想到用这种办法，多做题，积累经验。

这篇关于A - Difference Row的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！