先挖坑
这道题主要是应用set和map吧……
然后和队友wa到自闭
对着数据跑的时候发现是一些边界条件考虑的不清楚
不如先贴代码啦！（附文件读入1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
using namespace std;
struct node{
long long f,s;
}a[100100];
bool cmp1(node x,node y){
if (x.f==y.f) return x.s>y.s;
return x.f>y.f;
}
long long m[100100];
int n;
set <long long> q;
set <long long>::iterator it1;
map <long long,int> mp;
int main(){
int T;
//freopen("in.txt","r",stdin); //输入重定向，输入数据将从in.txt文件中读取
//freopen("data.txt","w",stdout);
scanf("%d",&T);
while (T--){
scanf("%d",&n);
for (int tt=1;tt<=n;tt++){
scanf("%lld%lld",&a[tt].f,&a[tt].s);
mp[a[tt].s]++;
q.insert(a[tt].s);
}
sort(a+1,a+1+n,cmp1);
m[1]=a[1].s;
m[0]=0;
for (int i=2;i<=n;i++){
m[i]=max(m[i-1],a[i].s);
}
long long ans=1e18;
for (int i=1;i<=n;i++){
mp[a[i].s]--;
if (mp[a[i].s]==0) q.erase(a[i].s);
long long maxx=a[i].f;
it1=q.lower_bound(maxx);
long long temp=m[i-1];
if(it1!=q.end()){
if(i!=1)ans=min(ans,abs(a[i].f-temp));
if((*it1)>=temp) ans=min(ans,abs(a[i].f-(*it1)));
if(it1!=q.begin()&&(*(--it1)>temp)) {
ans=min(ans,abs(a[i].f-(*it1)));
}
}
else{
ans=min(ans,abs(a[i].f-temp));
if(*(--it1)>temp) ans=min(ans,abs(a[i].f-*it1));
}
mp[a[i].s]++;
q.insert(a[i].s);
}
printf("%lld\n",ans);
mp.clear();
q.clear();
}
//fclose(stdin);
//fclose(stdout);
return 0;
}