Skip to content

14102: 【原4102】pilots

题目

题目描述

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

Description

小G想要成当飞行员,他现在拿到了一个飞行员测试的难度序列。 他希望在这个序列中找到一个最长的连续子序列,使得该子序列中任意两个难度的差值不会超过他设定的最大值K。

Input Format

第一行两个有空格隔开的整数k(0<=k<=2000,000,000),n(1<=n<=3000,000),k代表小G设定的最大值,n代表难度序列的长度。 第二行为n个由空格隔开的整数ai(1<=ai<=2000,000,000),表示难度序列。

Output Format

最大的字串长度。

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];
inline int read() {
    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() {
    k = read(); n = read();
    for (register int i = 0; i < n; ++i) {
        a[i] = read();
        // 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 read(){
    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(){
    k = read(), n = read();
}
void solve(){
    int lst = 0;
    int ans = 0;
    hdmin = tlmin = hdmax = tlmax = 0;
    for (int i = 1; i <= n; ++i){
        int a = read();
        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;
}