POI 2009/2010 Pilots

リンク

www.acmicpc.net

問題概要

要素数Nの数列Aが与えられる。区間内の(最大値)-(最小値)を満たすような数列Aの連続する区間で最長の長さを求めよ。

制約

考察

区間の最大値、最小値を見ていく問題ではスライド最小値(最大値)の考え方で解けるものが多く、今回もその要領で解くことが出来ます。

(ざっくりとした流れ)

見る区間の上限のindex iを0から順に見ていく

昇順と降順に並んだdequeを二つ持って今見てる要素がdequeの末端に来るまでpop_backしていく

尺取り法の要領で区間の左端のindex jも保持しておき、区間の最大値-最小値の条件を満たすまでpop_frontしていく　この時左端のindexをインクリメントしていく

そして(i-j+1)がiを右端とした時の最大の区間の長さとなるので答えの最大値を更新していく　計算量は

実装

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;
typedef long long int ll;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int t,n; cin >> t >> n;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	int ans=1;
	int j=0;
	deque<int> u,d;
	for(int i=0;i<n;i++){
		while(u.size()&&a[u.back()]>=a[i])u.pop_back();
		while(d.size()&&a[d.back()]<=a[i])d.pop_back();
		u.push_back(i);
		d.push_back(i);
		while(a[d.front()]-a[u.front()]>t){
			if(d.front()==j)d.pop_front();
			if(u.front()==j)u.pop_front();
			j++;
		}
		ans=max(ans,i+1-j);
	}
	cout << ans << endl;
}