Skip to content

14248: 【原4248】区间差

题目

题目描述

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

区间差

题目描述

有两个长度为\(n\)的序列\(\lbrace a_i\rbrace\)和\(\lbrace b_i\rbrace\)
对于一个区间\([l, r)\),并有\(f(l, r) = max(a_x) - min(b_y)\)其中\(x, y \in [l, r)\)
求出\(f(l, r)\)最大时\(r - l\)的最小值,它显然需要是个正数

输入格式

第一行两个数\(n\),表示序列长
第二行\(n\)个数,表示序列\(\lbrace a_i\rbrace\)
第三行\(n\)个数,表示序列\(\lbrace b_i\rbrace\)

输出格式

一个数表示\(r - l\)的最大值

样例输入

2
1 2
0 0

样例输出

1

数据规模

对于30%的数据有
\(n \leq 100\)
对于50%的数据有
\(n \leq 3000\)
对于另外20%的数据有
序列中没有数值相同的数
对于100%的数据有
\(n \leq 100000\)

yyong119's solution

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N 100010
#define min(x, y) ((x) < (y) ? (x) : (y))
using namespace std;
struct Node {
    int x, val;
} a[MAX_N], b[MAX_N];
int n, xa, xb, ans = 0x7fffffff;
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res * flag;
}
inline bool cmp_asc(const Node &p, const Node &q) {
    return p.val == q.val ? p.x < q.x : p.val < q.val;
}
inline bool cmp_dec(const Node &p, const Node &q) {
    return p.val == q.val ? p.x < q.x : p.val > q.val;
}
int main() {
    n = read();
    for (register int i = 0; i < n; ++i) {
        a[i].val = read(); a[i].x = i;
    }
    for (register int i = 0; i < n; ++i) {
        b[i].val = read(); b[i].x = i;
    }
    sort(a, a + n, cmp_dec);
    sort(b, b + n, cmp_asc);

    // 0 ~ xa have the same maximum value with index ascending
    while (xa < n - 1 && a[xa].val == a[xa + 1].val) ++xa;
    // 0 ~ xb have the same minimum value with index ascending
    while (xb < n - 1 && b[xb].val == b[xb + 1].val) ++xb;

    for (register int i = 0, j = 0; i <= xa && j <= xb; ) {
        // printf("###%d %d %d %d\n", i, j, a[i].x, b[j].x);
        ans = min(ans, abs(a[i].x - b[j].x));
        // printf("%d\n", ans + 1);
        if (a[i].x < b[j].x) ++i;
        else ++j;
    }
    printf("%d", ans + 1);
    return 0;
}

zqy2018's solution

#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 n;
pair<int, int> a[100005], b[100005];
int lst[100005], tot = 0;
void init(){
    n = read();
    for (int i = 1; i <= n; ++i)
        a[i].first = -read(), a[i].second = i;
    for (int i = 1; i <= n; ++i)
        b[i].first = read(), b[i].second = i;
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; ++i){
        if (a[i].first != a[1].first)   
            break;
        lst[++tot] = a[i].second;
    }
}
void solve(){
    int ans = n + 1, cur = 1;
    lst[0] = 0, lst[tot + 1] = n + 1;
    for (int i = 1; i <= n; ++i){
        if (b[i].first != b[1].first)   
            break;
        while (b[i].second > lst[cur])
            ++cur;
        if (cur - 1 != 0) ans = min(ans, b[i].second - lst[cur - 1]);
        if (cur != tot + 1) ans = min(ans, lst[cur] - b[i].second);
    }
    printf("%d\n", ans + 1);
}
int main(){
    init();
    solve();
    return 0;
}