TENKA1_2018_C - Align #27
Description
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;
}