# 14102: 【原4102】pilots

### 题目描述

author: poi 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4102

## Sample Input

``````3 9
5 1 3 5 8 6 6 9 10
``````

## Sample Output

``````4
``````

## FineArtz's solution

``````/* pilots */
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

const int INF = 2147483647;

int k, n, a[3000005];
pair<int, int> qmin[3000005], qmax[3000005];

bool check(int len){
memset(qmin, 0, sizeof(qmax));
memset(qmax, 0, sizeof(qmax));
int frontMin = 0, rearMin = 0;
int frontMax = 0, rearMax = 0;
qmin[rearMin++] = make_pair(0, 0);
qmax[rearMax++] = make_pair(0, INF);
for (int i = 1; i <= n; ++i){
while (frontMin != rearMin && qmin[frontMin].first <= i - len)
++frontMin;
while (frontMax != rearMax && qmax[frontMax].first <= i - len)
++frontMax;
while (frontMin != rearMin && a[i] <= qmin[rearMin - 1].second)
--rearMin;
qmin[rearMin++] = make_pair(i, a[i]);
while (frontMax != rearMax && a[i] >= qmax[rearMax - 1].second)
--rearMax;
qmax[rearMax++] = make_pair(i, a[i]);
if (i < len)
continue;
if (qmax[frontMax].second - qmin[frontMin].second <= k)
return true;
}
return false;
}

int main(){
cin >> k >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
int l = 1, r = n, mid;
while (l < r){
mid = (l + r) / 2 + (l + r) % 2;
if (check(mid))
l = mid;
else
r = mid - 1;
}
cout << l << endl;
return 0;
}
``````

## ligongzzz's solution

``````#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

uint32_t n, k;
cin >> k >> n;

multiset<uint32_t> sdata;
vector<uint32_t> vdata(n);
uint32_t cur_ans = 0u;
for (uint32_t i = 0u, cur_left = 0u; i < n; ++i) {
cin >> vdata[i];
sdata.insert(vdata[i]);
for (; *sdata.rbegin() - *sdata.begin() > k; sdata.erase(sdata.find(vdata[cur_left++])));
cur_ans = i - cur_left + 1u > cur_ans ? i - cur_left + 1u : cur_ans;
}

cout << cur_ans;

return 0;
}
``````

## yyong119's solution

``````#include<cstdio>
#define max(x, y) ((x) > (y) ? (x) : (y))
#define MAX_N 3000010
using namespace std;
int n, k, ans, h1, t1 = -1, h2, t2 = -1, tmp;
int a[MAX_N], q1[MAX_N],q2[MAX_N];
char ch = getchar(); int res = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9')
res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return res;
}
int main() {
for (register int i = 0; i < n; ++i) {
// q1 interval maximum
while (h1 <= t1 && a[i] >= a[q1[t1]]) --t1;
// q2 interval minimum
while (h2 <= t2 && a[i] <= a[q2[t2]]) --t2;
// enqueue
q1[++t1] = i; q2[++t2] = i;
while (a[q1[h1]] - a[q2[h2]] > k)
tmp = q1[h1] < q2[h2] ? q1[h1++] + 1 : q2[h2++] + 1;
// if (q1[h1] < q2[h2]) tmp = q1[h1++] + 1;
// else tmp = q2[h2++] + 1;
ans = max(ans, i - tmp);
}
printf("%d", ans + 1);
}
``````

## zqy2018's solution

``````/*
Hint: use two monotonic queues (one for max and one for min)
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int k, n;
int qmin[3000005][2], qmax[3000005][2];
int hdmin, tlmin, hdmax, tlmax;
void init(){
}
void solve(){
int lst = 0;
int ans = 0;
hdmin = tlmin = hdmax = tlmax = 0;
for (int i = 1; i <= n; ++i){
while (tlmax > hdmax && qmax[tlmax - 1][0] <= a)
--tlmax;
qmax[tlmax][0] = a, qmax[tlmax++][1] = i;
while (tlmin > hdmin && qmin[tlmin - 1][0] >= a)
--tlmin;
qmin[tlmin][0] = a, qmin[tlmin++][1] = i;
while (qmax[hdmax][0] - qmin[hdmin][0] > k){
++lst;
if (qmax[hdmax][1] == lst) ++hdmax;
if (qmin[hdmin][1] == lst) ++hdmin;
}
ans = max(ans, i - lst);
}
printf("%d\n", ans);
}
int main(){
init();
solve();
return 0;
}
``````