题目概述

CF1435C

解题报告

将 $a$ 排序，令 $B_{i,j}=b_i-a_j$ 。

我们可以枚举 $x$ ，然后对于每个 $i$ 我们采用第一个 $\ge x$ 的 $B_{i,j}$ ，然后求最大值减最小值。或者对于每个 $i$ 采用第一个 $\le x$ 的 $B_{i,j}$ ，然后求最大值减最小值。所有 $x$ 中最小的差距就是答案。

显然 $x$ 没必要枚举 $[1,10^9]$ ，只要 $6n$ 个数之间枚举就行了，扫描的时候用线段树维护最大值和最小值。

示例程序

#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=100000,maxm=maxn*6;

int a[6],n,b[maxn+5][6],m,ans;pair<int,int> c[maxm+5];
int MIN[(maxn<<2)+5],MAX[(maxn<<2)+5];

inline bool cmp(const pair<int,int> &x,const pair<int,int> &y) {return b[x.fr][x.sc]<b[y.fr][y.sc];}
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
void Insert(int pos,int k,int l=1,int r=n,int p=1){
    if (l==r) {MIN[p]=MAX[p]=k;return;} int mid=l+(r-l>>1);
    if (pos<=mid) Insert(pos,k,l,mid,p<<1); else Insert(pos,k,mid+1,r,p<<1|1);
    MIN[p]=min(MIN[p<<1],MIN[p<<1|1]);MAX[p]=max(MAX[p<<1],MAX[p<<1|1]);
}
int main(){
    for (int i=0;i<6;i++) scanf("%d",&a[i]);sort(a,a+6);
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        int x;scanf("%d",&x);
        for (int j=0;j<6;j++) b[i][j]=x-a[j],c[++m]=mp(i,j);
    }
    sort(c+1,c+1+m,cmp);
    for (int i=1;i<=n;i++) Insert(i,b[i][0]);
    ans=MAX[1]-MIN[1];
    for (int i=1;i<=m;i++){
        Insert(c[i].fr,b[c[i].fr][c[i].sc]);
        ans=min(ans,MAX[1]-MIN[1]);
    }
    for (int i=n;i;i--) Insert(i,b[i][5]);
    ans=min(ans,MAX[1]-MIN[1]);
    for (int i=m;i;i--){
        Insert(c[i].fr,b[c[i].fr][c[i].sc]);
        ans=min(ans,MAX[1]-MIN[1]);
    }
    printf("%d\n",ans);return 0;
}