CF1413C Perform Easily 题解

解题思路

其实是很简单的一道题，考虑计算出所有 \(b_i\) 在减去每一个 \(a_j\) 后所有可能的值，将这个值按照从小到大的顺序排序，那么我们可以考虑固定最小值，查找最大值，这个时候从最小值到最大值的区间内应该每一种 \(b_i\) 都出现了一次。那么，我们可以使用一个桶或者 map 搭配双指针来维护。

该种做法时间复杂度 \(O(6\times n\log n)\)。

其实可以再优化一点的。显然，上面的做法会计算一些重复的值，我们考虑去除这些重复的值。不难想到，两个相同的 \(b_i\)，删去一个后答案不变，同理，两个相同的 \(a_j\)，删除一个后答案不变，那么我们可以把 \(a\) 和 \(b\) 去重后再进行计算，时间复杂度 \(O(1)\sim O(6\times \log n)\)。

AC 代码

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include <set>
#include <valarray>
#include <map>
#define N 100005
#define M 800
int n,a[10],b[N];
struct Point{
    int val;
    int pos;
}A[N<<3];int m;
inline bool cmp(Point x,Point y){
    return x.val<y.val;
}
signed main(){
    scanf("%d%d",&a[1],&a[2]);
    scanf("%d%d",&a[3],&a[4]);
    scanf("%d%d",&a[5],&a[6]);
    scanf("%d",&n);
    std::sort(a+1,a+6+1);
    int t=std::unique(a+1,a+7)-a-1;
    for(register int i=1;i<=n;++i)
        scanf("%d",&b[i]);
    std::sort(b+1,b+n+1);
    n=std::unique(b+1,b+n+1)-b-1;
    for(register int i=1;i<=n;++i)
    for(register int j=1;j<=t;++j)
        A[++m]={b[i]-a[j],i};
    std::sort(A+1,A+m+1,cmp);
    int r=0,ans=2e9+7,res=0;
    std::map<int,int> cnt;
    for(register int i=1;i<=m;++i){
        while(r<m&&res<n){++r;
            if(!cnt[A[r].pos]) 
                ++res;
            ++cnt[A[r].pos];
        }if(res<n) break;
        if(A[r].val-A[i].val<ans)
            ans=A[r].val-A[i].val;
        --cnt[A[i].pos];
        if(!cnt[A[i].pos]) --res;
    }printf("%d",ans);
}