Codeforces Round #688 (Div. 2) : B번

codeforces.com/contest/1453/problem/B

Problem - B - Codeforces

문제 : 길동이가 실행할 수 있는 행동은 2가지 입니다.

1)suffix of array 의 원소들을 1씩 전부 증가

2)suffix of array 의 원소들을 1씩 전부 감소

 

suffix of arrary : 오른쪽부터 n번째 원소까지의 집합을 뜻합니다.

 

이때,길동이는 하나의 원소를 자신이 원하는 원소로 최소 1번 바꿀 수 있습니다.(바꾸지 않을 수도 있다는 뜻입니다.)

모든 원소들의 값들이 동일한 원소가 될때까지 몇번 길동이는 행동을 해야하는지 최소값을 구하는게 문제입니다.

 

해설 : 먼저 당장은 길동이가 원소값을 변경하는 것을 생각하지 말고 주어진 상황에서 어떻게 하면 최적의 값을 구할 수 있을지 부터 생각해 봅시다.

예를 들어서 현재 배열에 

99 96 97 95

의 값들이 들어가 있을때, suffix of array를 전체를 잡았을때를 생각해보면 굳이 할 필요성이 없겠죠?모든 원소값들이 변경되니 영영 동일한 원소로 맞추지 못할테니까요.

그러면 맨처음 값은 나두고 2번째 원소까지 suffix를 잡으면 결국은 맨처음값(99)에 모든 원소들을 맞추어야 한다는 것을 우리는 알 수 있습니다.

(96->99 : +3) , (97->100->99 : +3 -1) , (95->98->97->99 : +3 -1 +2) : 총 (3 + 1 + 2) 6번의 행동이 필요합니다.

이를 유심히 관찰하면 결국은 현재 원소(i) 와 전 원소(i-1)의 차이들의 합이라는 것을 발견할 수 있죠.

우린 이를 sum 이라고 정의를 하겠습니다. 저희들의 목표는 이 원소들 중 하나의 값을 변경하여 이 sum을 가장 최소값으로 만드는게 목표입니다.

 

자 그럼 이제 원소를 바꾸는 것을 생각해 봅시다.

만약 처음 원소인 99->96로 변경했다고 해보면 우린 3의 이득을 취할 수 있습니다.

그리고 마지막 원소인 95->97로 변경했다고 하면 우린 2의 이득을 취할 수 있죠.

 

그런데 문제는 그럼 가운데 원소를 바꾸었을땐 어떻게 되는가?입니다.

96->99로 변경하였을때 

99 99 97 95

가 되고, 이러면 단 4번만에 모든 원소를 동일한 원소로 만들 수 있습니다.

그럼 하나씩 살펴보면 기존 99 96 97 95 의 원소들간 ai 와 ai-1 의 차이값을 적어보면 3 1 2 가 되죠.

num[] : 99 96 97 95

arr[] :        3   1  2

이때 96->99 변경하면

num[] : 99 99 97 95

arr[] :        0   2  2 

가 됩니다....뭐가 보이시나요??

바로 현재 바꾼 원소의 arr 의 값은 사라지게 되고 오른쪽 원소는 arr[i + 1] - abs(num[i-1] - num[i + 1]) 만큼 증가한 것을 알 수 있습니다.

96을 오른쪽 원소인 97로 바꾸어서 계산해 봐도 결국 똑같은걸 확인하 실 수 있으실 겁니다.

 

1) ans = min(ans,arr[1])

2) ans = min(ans,arr[n-1])

3) ans = min(ans,sum - arr[i] - (arr[i+1]-abs(num[i-1]-num[i+1]))) 

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll num[200000],arr[200000];

void solve();

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

	while (t--)
		solve();
}
void solve()
{
	ll n,sum=0;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> num[i];
	for (int i = 1; i < n; i++) {
		arr[i] = abs(num[i - 1] - num[i]);
		sum += arr[i];
	}
	ll ans = sum;

	ans = min(ans, sum - arr[1]);
	ans = min(ans, sum - arr[n - 1]);

	for (int i = 1; i < n-1; i++) {
		ans = min(ans, sum - arr[i] - (arr[i + 1] - abs(num[i-1] - num[i + 1])));
		ans = min(ans, sum - arr[i + 1] - (arr[i] - abs(num[i - 1] - num[i+1])));
	}
	cout << ans << "\n";
}