CF1801B Buying gifts 题解

· · 题解

题目大意

给定 n 个商店，每个商店分别可以给 A 、 B 两个人买价值为 a_i 、 b_i 的商品，求两人商品最大值之差的最小值

题解

首先考虑时间复杂度， 2≤n≤5×10^5 ，不难算出是个 O(n log n) 的算法，可以考虑用 set 做，再结合后缀最大值和 lower _ bound，即可求解

首先将 a_i 从小到大排序，用 maxv_i 去存储 b_i 到 b_n 中的最大值。对于每个 b_i ，都需要用 set 存储，考虑每个 ai ，ans 应等于 min(ans,abs(maxv_i-a_i)) ，用 lower _ bound 去找到 set 中第一个大于等于 a_i 的值的位置，记作 it ， 如果 it 不是 set 的末尾，就用 C 去存储 it 所对应的值，如果 it 不是 set 的开头，就用 D 去存储 it-1 所对应的值，最后判断 C 、 D 分别是否大于 B ，如果是，则分别取最小值，再向 set 中加入 b_i 。最后输出最小值即可。

因为是多组数据，所以每次操作完之后都要清空 set 和 maxv （但是第一次 AC 没有清空 maxv 蒟蒻也过了）

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T;
const int M=500005;
int n,maxv[M],ans;
set<int> s;
struct node{
    int a,b;
}p[M];
bool cmp(node x,node y){
    return x.a<y.a;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i) scanf("%d%d",&p[i].a,&p[i].b);
        sort(p+1,p+1+n,cmp);
        maxv[n+1]=-1;//初始化为-1即可 
        for(int i=n;i>=1;--i) 
            maxv[i]=max(maxv[i+1],p[i].b);//取b[i]到b[n]中的最大值 
        s.clear();
        ans=abs(p[1].a-maxv[2]);
        s.insert(p[1].b);
        for(int i=2;i<=n;++i){
            int A=p[i].a,B=maxv[i+1],C=-1,D=-1;
            if(i<n) ans=min(ans,abs(A-B));
            set<int>::iterator it=s.lower_bound(A);//寻找s中第一个不小于A的值 
            if(it!=s.end()) C=*it;
            if(it!=s.begin()) D=*(--it);
            if(C>B) ans=min(ans,abs(A-C));
            if(D>B) ans=min(ans,abs(A-D));
            s.insert(p[i].b);
        }
        printf("%d\n",ans);
        s.clear();//一定要清空 
        memset(maxv,0,sizeof(maxv));
    }
    return 0;
}