백준 및 코드포스

You are given an array 𝑎a of length 𝑛n. We define the equality of the array as the number of indices 1≤𝑖≤𝑛−11≤i≤n−1 such that 𝑎𝑖=𝑎𝑖+1ai=ai+1. We are allowed to do the following operation:

• Select two integers 𝑖i and 𝑥x such that 1≤𝑖≤𝑛−11≤i≤n−1 and 1≤𝑥≤1091≤x≤109. Then, set 𝑎𝑖ai and 𝑎𝑖+1ai+1 to be equal to 𝑥x.

Find the minimum number of operations needed such that the equality of the array is less than or equal to 11.

Each test contains multiple test cases. The first line contains a single integer 𝑡t (1≤𝑡≤1041≤t≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer 𝑛n (2≤𝑛≤2⋅1052≤n≤2⋅105) — the length of array 𝑎a.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤1091≤ai≤109) — elements of the array.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 2⋅1052⋅105

For each test case, print the minimum number of operations needed.

배열에서 arr[i] == arr[i + 1] 이 되는 경우가 최대 1회가 되도록 하는 문제입니다.

임의로 x를 골라서 arr[x]와 arr[x + 1]을 내가 원하는 값으로 바꿔주는 작업을 해줄 수 있습니다.

위의 작업을 하는 최소의 경우를 찾으면 됩니다.

예를 들어

1 1 2 5 4 1 1

이런 배열을 받은 경우 결국 양 끝의 2개가 있는 지점에서부터 가운데로 좁혀와서 중복되는 숫자를 없애줘야 최솟값이 됩니다.

1 1 2 5 7 7 1 -> 1 9 9 5 7 7 1 -> 1 9 8 8 7 7 1 -> 1 9 8 3 3 7 1

양 끝에서 연속되는게 언제 등장하는지 구해서 그 사이만큼 저렇게 변화시키는 값을 구해주면 됩니다.

#include <stdio.h>
int main() {
    int t;
    int arr[200001] = {};
    scanf("%d", &t);
    for(int i = 0; i <t; i++) {
        int n, temp = 0;
        scanf("%d", &n);
        for(int j = 0; j < n; j++) {
            scanf("%d", &arr[j]);
        }
        int count = 1, cc = 0;
        int startpoint = 0, end = 0;
        for(int j = 1; j < n; j++) {
            if(arr[j] == arr[j - 1]) {
                startpoint = j;
                break;
            }
        }
        for(int j = n - 1; j > 0; j--) {
            if(arr[j] == arr[j - 1]) {
                end = j;
                break;
            }
        }
        if(end - startpoint < 1) cc = 0;
        else if(end - startpoint <= 2) cc= 1;
        else cc = end - startpoint -1;
        printf("%d\n", cc);
    }
}