백준 3988번 수 고르기

문제 링크입니다: https://www.acmicpc.net/problem/3988

슬라이딩 윈도우 기법을 이용하여 푸는 문제였습니다.

백준 2905번 홍준이와 울타리(http://jaimemin.tistory.com/832)처럼 monotone queue를 이용하여 푸는 문제였습니다.

#include <iostream>

#include <deque>

#include <algorithm>

using namespace std;

 

const int MAX = 1000000;

const int INF = 987654321;

 

int arr[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N, K;

        cin >> N >> K;

 

        for (int i = 0; i < N; i++)

                 cin >> arr[i];

 

        sort(arr, arr + N);

        deque<int> dq; //idx

        int result = INF;

 

        K = N - K;

        //슬라이딩 윈도우

        for (int i = 0, j = 1; i + K <= N; i++)

        {

                 if (!dq.empty() && dq.front() <= i)

                         dq.pop_front();

 

                 //K개씩 확인

                 for ( ; j < i + K; j++)

                 {

                         //arr[j] - arr[j - 1]이 최대여야한다

                         while (!dq.empty() && arr[j] - arr[j - 1] <= arr[dq.back()] - arr[dq.back() - 1])

                                 dq.pop_back();

                         dq.push_back(j);

                 }

 

                 int m = arr[dq.front()] - arr[dq.front() - 1]; //맨 앞 두 개의 차

                 int M = arr[i + K - 1] - arr[i]; //양 끝 차

                 result = min(result, m + M);

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~