[Codeforces Round 981(Div.3)] - C. Sakurako's Field Trip

https://codeforces.com/contest/2033/problem/C

Codeforces Round 981(Div.3) - C. Sakurako's Field Trip

문제 유형: 투 포인터, 그리디

시간 제한: 2초

메모리 제한: 256MB

 

문제

Even in university, students need to relax. That is why Sakurakos teacher decided to go on a field trip. It is known that all of the students will be walking in one line. The student with index i has some topic of interest which is described as a_i.

As a teacher, you want to minimise the disturbance of the line of students.

The disturbance of the line is defined as the number of neighbouring people with the same topic of interest.

In other words, disturbance is the number of indices j(1≤j<n) such that aj=aj+1.

In order to do this, you can choose index i(1≤i≤n) and swap students at positions i and n−i+1.

You can perform any number of swaps.

Your task is to determine the minimal amount of disturbance that you can achieve by doing the operation described above any number of times.

 

대학교에서도 학생들은 휴식이 필요하다.

Sakurako 일행과 선생님은 야외수업을 왔다.

학생들은 한 줄로 서서 걷고 있다.

인덱스 i의 student는 a_i번의 관심사를 가지고 있다.

선생님으로써, 당신은 학생들의 혼란을 줄여야 한다.

선의 혼란은 같은 관심사의 학생들이 얼마나 인접해있는지에 대한 것이다.

즉, a_j = a_{j+1} (1 <= j < n)인 쌍의 개수이다.

당신은 해결하기 위해, 반대편의 대응되는 학생과 자리를 바꾸게 할 수 있다.

몇 번이고 할 수 있다.

자리를 바꾸게 한 뒤의 최소 혼란의 합을 구하시오.

 

 

입력

The first line contains one integer t (1≤t≤10^4) — the number of test cases.

Each test case is described by two lines.

The first line contains one integer n(2≤n≤10^5) — the length of the line of students.

The second line contains nintegers ai (1≤ai≤n) — the topics of interest of students in line.

 

It is guaranteed that the sum of n across all test cases does not exceed 2⋅10^5.

 

첫 줄로 테스트케이스의 수 t가 주어지는데, 테스트케이스 t는 10000이하입니다.

각 테스트케이스의 첫 줄에서는 n(2 ~ 100000)이 주어집니다. 학생들의 수입니다.

각 테스트케이스의 두 번째 줄에는 a_i가 주어집니다. 학생들의 관심사 번호가 n개로 주어집니다.

전체 TC에 대한 n의 합이 2*10^5를 넘지 않습니다.

 

출력

For each test case, output the minimal possible disturbance of the line that you can achieve.

각 테스트케이스별로 만들 수 있는 최소의 혼란도를 구하시오.

 

풀이

 

위 그림과 같은 4가지의 길이가 4인 학생들의 라인을 고려해보자.

1,2,3의 경우는 안쪽 요소에 대해서 swap을 해도 혼란도가 바뀌지 않는다.

4번, 즉 양쪽 다 겹치치 않는 경우만, swap을 할 시 혼란도가 1늘어난다.

 

양쪽의 쌍에서 하나라도 겹친다면, 우선 뒤집어보면 된다. 이미 하나라도 겹치는 쌍이 있다면, 더 겹치는 쌍이 생길 걱정은 없다.

오히려 겹치는 게 줄어들거나, 또는 그저 개수가 유지될 뿐이다.

 

이렇게 무작정 양 쪽의 쌍들을 순차적으로 보면서 한 번 뒤집어준 다음, 배열을 다시 순회하면서 값을 누적해서 출력해주면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> arr(n);
  for (int i = 0; i < n; ++i) {
    cin >> arr[i];
  }

  for (int i = 1; i < n / 2; ++i) {
    if (arr[i - 1] == arr[i] || arr[n - i - 1] == arr[n - i]) {
      swap(arr[i], arr[n - i - 1]);
    }
  }

  int ans = 0;
  for (int i = 1; i < n; ++i) {
    if (arr[i - 1] == arr[i])
      ans++;
  }
  cout << ans << "\n";
}

int main(int argc, char *argv[]) {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}