백준 11003 최솟값 찾기

백준 11003
N이 최대 오백만개이기 때문에 적어도 NlogN으로 풀어야 시간초과가 나지 않는다. 그러기 위해서는 우선순위 큐를 이용한 풀이법이 필요하다.
Di는 A(i-L+1) ~ Ai 까지의 최솟값을 도출해내야한다.
i-l+1은 음수값이 나올 수 있지만 Di에 무조건 Ai의 값은 포함되어야 한다. -> for 문으로 D1~Dn까지 값을 구해주면 된다.

1. 우선순위 큐에 N개의 수를 첫번째부터 값과 인덱스 두 값을 넣어준다.
   (이 때, 우선순위큐는 최소힙을 구성해야 한다.)
2. 우선순위 큐의 top 값은 최소값이 되고 그 값의 인덱스 값으로 구성되어 있다. Di는 A(i-L+1) ~ Ai 중의 최솟값임으로 만약 우선순위 큐의 top의 인덱스가 A(i-L+1) ~ Ai에 포함되어 있지 않다면 pop 을 해주면 된다.

#include<bits/stdc++.h>
using namespace std;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>pq;
int n, l;
int arr[5000001];
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n >> l;

	for (int i = 1; i <= n; i++) cin >> arr[i];

	for (int i = 1; i <= n; i++) {
		pq.push({ arr[i],i });
		int x = pq.top().second;
		while (x < i - l + 1) {
			pq.pop();
			x = pq.top().second;
		}

		cout << pq.top().first << ' ';
	}

}