Maximise Adjacent Sum Codechef Solution || Codechef contest solution

,

You are given an array A of size (N≥2).

We define

(

)

1


1
(


+


+
1
)
f(A)=∑
i=1
N−1

(A
i

+A
i+1

).

Find the maximum value of

(

)
f(A) you can obtain by rearranging the elements of

A in any arbitrary order.

Input Format
The first line of input will contain a single integer

T, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains one integer,

N, the size of the array.
The next line contains

N space-separated integers,

1
,

2
,

,


A
1

,A
2

,…,A
N

.
Output Format
For each test case, output on a new line, the maximum value of

(

)
f(A) you can obtain by rearranging the elements of

A in any arbitrary order.

Constraints
1



2

1
0
4
1≤T≤2⋅10
4

2



1
0
5
2≤N≤10
5

1




1
0
4
1≤A
i

≤10
4

The sum of

N over all test cases does not exceed
1
0
5
10
5
.
Sample 1:
Input
Output
2
2
3 6
5
2 2 1 2 2
9
15
Explanation:
The first sample has
2
2 valid arrays :
[
3
,
6
]
[3,6] and
[
6
,
3
]
[6,3], both have

(

)

9
f(A)=9.

For the second sample, one optimal array is
[
1
,
2
,
2
,
2
,
2
]
[1,2,2,2,2], which has

(

)

f(A)=
(
1
+
2
)
+
(
2
+
2
)
+
(
2
+
2
)
+
(
2
+
2

)

15
(1+2)+(2+2)+(2+2)+(2+2)=15.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }

        sort(arr.begin(), arr.end(), greater<int>());

        long long sum = 0;
        for (int i = 0; i < n - 1; i++) {
            sum += arr[i] + arr[i + 1];
        }

        cout << sum << endl;
    }

    return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *