Zlung

2018 Tenka1 C - Align

Table of Contents

Problem description

Origin

https://tenka1-2018-beginner.contest.atcoder.jp/tasks/tenka1_2018_c

Problem analysis

Let B{B} be the ascending order of A{A}. The maximum sum mostly in such two order:

B1,BN,B2,BN−1,…B_1,B_N,B_2,B_{N-1},\ldots

BN,B1,BN−1,B2,…B_N,B_1,B_{N-1},B_2,\ldots

It is correct when NN is even. If NN is odd, we should consider the place of B(1+N)/2B_{(1+N)/2}. Let Bmid=B(1+N)/2B_{mid}=B_{(1+N)/2}. Refer the above example, we can get the similarity idea:

Bmid,B1,BN,…,Bmid−1,Bmid+1B_{mid},B_1,B_N,\ldots,B_{mid-1},B_{mid+1}

B1,BN,…,Bmid−1,Bmid+1,BmidB_1,B_N,\ldots,B_{mid-1},B_{mid+1},B_{mid}

Bmid,BN,B1,…,Bmid+1,Bmid−1B_{mid},B_N,B_1,\ldots,B_{mid+1},B_{mid-1}

BN,B1,…,Bmid+1,Bmid−1,BmidB_N,B_1,\ldots,B_{mid+1},B_{mid-1},B_{mid}

AC code

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

#define INF 0xc0c0c0c0
#define NINF 0x3f3f3f3f

#define FOR(i, a, b) for((i)=a; i<b; ++(i))
#define EFOR(i, a, b) for((i)=a; i>b; --(i))

#define MLC(n, type) (type*)malloc(n*sizeof(type))
#define CLC(n, type) (type*)calloc(n, sizeof(type))

#define MAXN 100000+2

void solver(int *nums, int numsSize) {
	int i = 0, j = numsSize - 1;
	long long int sum1 = 0, sum2 = 0;
	sort(nums, nums+numsSize);

	for (i = 0; i+1<=j-1; ++i,--j) {
		sum1 += nums[j] + nums[j-1] - (nums[i]<<1);
		sum2 += (nums[j]<<1) - nums[i] - nums[i+1];
	}

	if (i == j) {
		sum1 = max(sum1, sum1 - nums[i] + nums[i-1] + nums[numsSize-1] - nums[i]);
		sum2 = max(sum2, sum2 - nums[j+1] + nums[i] + nums[i] - nums[0]);
	}
	else {
		sum1 += max(nums[numsSize-1] - nums[i], nums[j] - nums[i]);
		sum2 += max(nums[j] - nums[0], nums[j] - nums[i]);
	}

	printf("%lld\n", max(sum1, sum2));
	return;
}

int main() {
	int i,n;
	int a[MAXN] = {0};

	scanf("%d", &n);

	FOR(i, 0, n) {
		scanf("%d", &a[i]);
	}

	solver(a, n);
	return 0;
}