Codeforces Round #772 (Div2) - B.Avoid Local Maximums

https://codeforces.com/contest/1635/problem/B

Problem - B - Codeforces

---

문제

 

You are given an array 𝑎a of size 𝑛. Each element in this array is an integer between 1 and 10^9.

You can perform several operations to this array. During an operation, you can replace an element in the array with any integer between 1and 10^9. 

Output the minimum number of operations needed such that the resulting array doesn't contain any local maximums, and the resulting array after the operations.

An element 𝑎𝑖ai is a local maximum if it is strictly larger than both of its neighbors (that is, ai>ai−1 and ai>ai+1). Since a1 and 𝑎𝑛an have only one neighbor each, they will never be a local maximum.

Each test contains multiple test cases. The first line will contain a single integer t (1≤t≤10000) — the number of test cases. Then 𝑡ttest cases follow.

The first line of each test case contains a single integer n (2≤𝑛≤2⋅10^5) — the size of the array 𝑎a.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤10^9), the elements of array.

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

Output

For each test case, first output a line containing a single integer 𝑚m — minimum number of operations required. Then ouput a line consist of 𝑛n integers — the resulting array after the operations. Note that this array should differ in exactly 𝑚m elements from the initial array.

If there are multiple answers, print any.

---

풀이

배열 중 인접한 두 수보다 크면 local maximum이라 정의한다. 이 문제는 이 local maximum을 없애는 문제이다.

그리디한 방법을 사용하면 되는데 배열 1 2 1 3 2 가 있다고 가정해보자.

여기서 두 번째 2는 local maximum으로 2를 1로 바꾸거나 오른쪽 1을 2나 3으로 바꾸는 방법이 있다.

오른쪽 1을 3으로 바꾸는 방법이 가장 효율적인데 그 이유는 한 번에 두 개의 local maximum (왼쪽에 2, 오른쪽에 3)을 동시에 없앨 수 있기 때문이다.

1. 1부터 시작하여 N까지 local maximum을 찾는다.
2. local maximum을 찾으면 바로 오른쪽의 수를 그 다음 오른쪽의 수와 local maximum 중 더 큰 값으로 바꾼다.

 

---

코드

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

void input() {
}

void init() {
}


void solution() {
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T,N,cnt;
    cin>>T;
    while(T--){
        cin>>N;
        vector<int> v;
        cnt=0; v.resize(N);
        
        for(int i=0;i<N;i++) cin>>v[i];
        
        // 마지막에 구간을 넘기는 것을 방지하기 위해 넣어준다.
        v.push_back(INT_MIN);
        
        for(int i=1;i<N-1;i++){
            // local maximum을 찾는다.
            if(v[i]>v[i-1]&&v[i]>v[i+1]){
                // 오른쪽의 수를 local maximum과 그 다음 오른쪽 수 중 큰 값으로 바꾼다.
                v[i+1]=max(v[i],v[i+2]);
                cnt++;
            }
        }
        v.pop_back();
        cout<<cnt<<endl;
        for(int i=0;i<N;i++) cout<<v[i]<<' ';
        cout<<endl;
        
    }
    return 0;
}