백준8201 pilots

작성일 | In

문제 링크

  • http://icpc.me/8201

문제 출처

  • POI 2009/2010 Stage3 8번

사용 알고리즘

  • Deque
  • Sliding Window

시간복잡도

  • O(n)

풀이

문제를 간단하게 요약하자면, N개의 수가 주어질 때 연속 구간 중 (구간 내 최댓값) - (구간 내 최솟값) ≤ T를 만족하는 최대 길이의 연속 구간을 찾는 문제입니다.

[1, 1]구간에서 시작해 Max - Min <= T를 만족할 때까지 구간의 끝점을 계속 뒤로 보냅니다.
더 이상 뒤로 가지 못 한다면 구간의 시작점을 뒤로 보냅니다.
이런식으로 구간의 길이를 최대화시키면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
#define val first
#define idx second
using namespace std;

typedef long long ll;
typedef pair<ll, int> p;

deque<p> dq1, dq2;

ll n, t;
int ans = 0, bound = 0;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> t >> n;
	for(int i=1; i<=n; i++){
		ll x; cin >> x;
		while(dq1.size() && dq1.back().val >= x) dq1.pop_back();
		while(dq2.size() && dq2.back().val <= x) dq2.pop_back();
		dq1.push_back({x, i});
		dq2.push_back({x, i});
		while(dq2.front().val - dq1.front().val > t){
			if(dq1.front().idx < dq2.front().idx){
				bound = dq1.front().idx;
				dq1.pop_front();
			}else{
				bound = dq2.front().idx;
				dq2.pop_front();
			}
		}
		ans = max(ans, i - bound);
	}
	cout << ans;
}