不知道为什么和 THUPC 的那道众数这么像。
题意简述
有长度为 $n$ 的数列 $a_n,b_n$ ，对于每个位置 $i$，我们只能选择 $a_i$ 或 $b_i$ ，求选择的 $|a_{max}-b_{max}|$。$(1\le n \le 5\times 10^5)$.
题意分析
我们有一个显然的 $\Theta(2^n)$ 的暴力，考虑优化这个暴力。
因为 $a_i$ 和 $b_i$ 同时对答案产生了贡献，我们不妨固定一个数列的贡献，具体地，我们枚举每一位 $i$，钦定 $a_i$ 为 $a$ 中做贡献的元素，即 这个数是选中的 $a$ 的最大值。
那么现在有两类位置，第一类位置 $p_1$ 是 $a_{p_1}$ 比 $a_i$ 小的，我们发现这些位置无论是选 $a$ 还是 $b$ 都没有影响，那我们就选 $|a-b|_{min}$ ；第二类位置 $p_2$ 是 $a_{p_2} 比 a_i$ 大的，这些位置中我们只能选 $b$ ，即 $|a-b|$ 已经确定。
这两种情况取最小的值就是 $a_i$ 为 $a_{max}$ 时的最小值，循环一遍就可以得到最后的答案，总的时间复杂度是 $\Theta(n\log n)$。
代码时间
代码使用 std::set 实现细节，注意判断是否是开头和结尾元素。
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
|
#define int long long
int n,m,k;
signed main(){
mul();
return 0;
}
int a[N],b[N],mb[N];
set<int>s;
struct node{
int a,b;
}f[N];
bool cmp(node x,node y){
return x.a<y.a;
}
void solve(){
read(n);
for(int i=1;i<=n+10;i++)mb[i]=0;
s.clear();
for(int i=1;i<=n;i++){
read(f[i].a,f[i].b);
}
sort(f+1,f+1+n,cmp);
for(int i=n;i>=1;i--){
mb[i]=max(mb[i+1],f[i].b);
}
mb[n+1]=-1;
int ans=1e12;
s.insert(-LINF);
for(int i=1;i<=n;i++){
int tmp1=-1,tmp2=-1;
if(!s.empty()){
auto it=s.lower_bound(f[i].a);
auto itt=prev(it);
if(it!=s.begin())tmp1=*itt;
if(it!=s.end())tmp2=*it;
tmp1=max(tmp1,mb[i+1]);tmp2=max(tmp2,mb[i+1]);
if(tmp1==-1)tmp1=INF;if(tmp2==-1)tmp2=INF;
}
ans=min(ans,min(abs(f[i].a-tmp1),abs(f[i].a-tmp2)));
s.insert(f[i].b);
}
writeh(ans);
}
|