DID : PS 1문제 (2023/04/11)

오늘은 미적 시험날.

BOJ 1306 달려라 홍준
문제는 일정한 길이의 구간이 오른쪽으로 이동하면서 각 구간에서 최댓값을 찾아내는 문제이다. 세그먼트 트리를 이용해서 구해낼 수도 있지만, 그것보다는 슬라이딩 윈도우 기법으로 돌려서 푸는 게 더 빠르다고 생각해서 그렇게 풀었다.

이게 플레5? 조금 부풀려졌다고 생각함

#include<bits/stdc++.h>
using namespace std;
priority_queue<int> see, del;
vector<int> vec;
int arr[(int)1e6+7];
int main()
{
    int n,m; scanf("%d %d",&n,&m);
    for(int i = 1; i<= n; i++) scanf("%d", arr+i);
    for(int i = 1; i<2*m-1; i++)
        see.push(arr[i]);
    for(int i = 2*m-1; i <= n; i++)
    {
        see.push(arr[i]);
        del.push(arr[i-(2*m-1)]);
        while(del.top() == see.top())
            del.pop(), see.pop();
        printf("%d ", see.top());
    }
}