TENKA1_2018_C - Align

[zeikar]

Problem link

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

Problem Summary

적당히 N개의 배열을 정렬해서 양 옆 원소의 차이의 절대값의 합의 최댓값을 구하는 문제.

Solution

먼저 어떻게 하면 최대가 될지 대충 생각해보면 큰 값, 작은 값이 번갈아가면서 나와야 한다.

아래부턴 에디토리얼을 참고함.

예시로 홀수 번째 인덱스가 큰 값들, 짝수 번째 인덱스가 작은 값들이라고 놓으면, 절대값을 한 결과는 (큰 값 - 작은 값)이 된다.

n = 5일 때,

(p1 − p2) + (p3 − p2) + (p3 − p4) + (p5 − p4) = (+1) ∗ p1 + (−2) ∗ p2 + (+2) ∗ p3 + (−2) ∗ p4 + (+1) ∗ p5.

이런 식이 되고, 계수가 큰 순서대로 큰 수를 넣어주면 최댓값을 얻을 수 있다.

반대로 짝수 번째 인덱스가 큰 값일 때는

(p2 − p1) + (p2 − p3) + (p4 − p3) + (p4 − p5) = (-1) ∗ p1 + (+2) ∗ p2 + (-2) ∗ p3 + (+2) ∗ p4 + (-1) ∗ p5.

이것도 마찬가지로 큰 계수부터 큰 수를 넣어주면 된다.
정답은 위 두 가지 중 큰 값을 출력하면 된다.

위 예시는 n이 홀수일 경우고 짝수인 경우는 한번만 해주면 된다.

Source Code

#include <iostream>
#include <algorithm>
using namespace std;

long long a[100000];

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

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

	sort(a, a + n);

	long long ans = 0;

	if (n % 2 == 0)
	{
		for (int i = 0; i < n / 2; i++)
		{
			ans -= 2 * a[i];
		}
		for (int i = n / 2; i < n; i++)
		{
			ans += 2 * a[i];
		}
		ans -= a[n / 2];
		ans += a[n / 2 - 1];
	}
	else
	{
		long long oddBig = 0, evenBig = 0;

		for (int i = 0; i < n / 2; i++)
		{
			oddBig -= 2 * a[i];
		}
		for (int i = n / 2; i < n; i++)
		{
			oddBig += 2 * a[i];
		}
		oddBig -= a[n / 2];
		oddBig -= a[n / 2 + 1];


		for (int i = 0; i <= n / 2; i++)
		{
			evenBig -= 2 * a[i];
		}
		for (int i = n / 2 + 1; i < n; i++)
		{
			evenBig += 2 * a[i];
		}
		evenBig += a[n / 2];
		evenBig += a[n / 2 - 1];

		ans = max(oddBig, evenBig);
	}


	cout << ans << endl;
}