# 14248: 【原4248】区间差

### 题目描述

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

# 区间差

## 样例输入

2
1 2
0 0


## 样例输出

1


## 数据规模

$$n \leq 100$$

$$n \leq 3000$$

$$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;
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() {
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 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(){
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;
}