[UVA][greedy] 11158 - Elegant Permuted Sum
|
You will be given n integers <A1A2A3...An>. Find a permutation of these n
integers so that summation of the absolute differences between adjacent
elements is maximized.
Suppose n = 4 and the given integers are <4 2 1 5>. The permutation <2 5 1 4> yields the maximum summation.
For this permutation sum = abs(2-5) + abs(5-1) + abs(1-4) = 3+4+3 = 10.
Of all the 24 permutations, you won�t get any summation
whose value exceeds 10. We will call this value, 10,
the elegant permuted sum.
Input
The first line of input is an integer T(T<100) that represents the number of test cases. Each case consists of a line that starts with n (1<n<51) followed by n non-negative integers separated by a single space. None of the elements of the given permutation will exceed 1000.
Output
For each case, output the case number followed by the elegant permuted summation.
|
Sample Input |
Output for Sample Input |
34 4 2 1 54 1 1 1 12 10 1 |
Case 1: 10 Case 2: 0Case 3: 9 |
Problem
Setter: Sohel Hafiz
Special Thanks: Jane Alam Jan
決定使用貪心，會發現一定是高低高低，要不然就是低高低高的方式。
很容易地會希望最高最低的盡可能在中間。
因此考慮兩種方式，先將低的放中間，旁邊兩個擺最高的，然後再放低的在兩側。
又或者先放高的的在中間。
將兩種情況比較一下即可。
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int main() {
int testcase, cases = 0;
int A[105];
scanf("%d", &testcase);
while(testcase--) {
int ret = 0;
int n, i, j;
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%d", &A[i]);
sort(A, A+n);
int front = 0, rear = n-2;
int l = (n-1)/2, r = (n-1)/2;
int B[105] = {};
B[l] = A[n-1];
while(front <= rear) {
B[++r] = A[front++];
if(front > rear) break;
B[--l] = A[front++];
if(front > rear) break;
B[++r] = A[rear--];
if(front > rear) break;
B[--l] = A[rear--];
}
for(i = 1; i < n; i++)
ret += abs(B[i]-B[i-1]);
front = 1, rear = n-1;
l = (n-1)/2, r = (n-1)/2;
B[l] = A[0];
while(front <= rear) {
B[++r] = A[rear--];
if(front > rear) break;
B[--l] = A[rear--];
if(front > rear) break;
B[++r] = A[front++];
if(front > rear) break;
B[--l] = A[front++];
}
int sub = 0;
for(i = 1; i < n; i++)
sub += abs(B[i]-B[i-1]);
ret = max(ret, sub);
printf("Case %d: %d\n", ++cases, ret);
}
return 0;
}