P10679 『STA - R6』 spec 题解

前言

怎么题解区全是假做法，这里提供一个和标解思路略微不同的方法。

思路

对于每个 $x_i$，设 $x_i=\lceil k\alpha\rceil-1$，解不等式可得 $x_i<k\alpha \leq x_i+1$，考虑枚举 $k$ 把不等式解集转化成一堆区间（即 $[\frac{x_i}{k}+eps,\frac{x_i+1}{k}]$），同时注意到答案保底为 $1$，于是可以忽略右端点在 $1$ 左边的区间，这样枚举到 $k$ 的上界就不会超过 $x_i$。

于是问题就变成了找到最大的、被每个 $x_i$ 形成的区间都覆盖过的数，而这个过程可以离散化后用差分解决；具体地，枚举每个 $x_i$，将其形成的所有区间都推平为 $1$，处理完之后将每个当前为 $1$ 的下标的 $sum$ 值都加上 $1$，最后 $sum=n$ 的下标就是合法的。

容易发现答案一定是某个区间的右端点，所以直接简单从右往左遍历找答案就做完了，如果没有找到就输出 $1$。

时间复杂度 $\mathcal{O}(\sum x\log \sum x)$，$\log$ 来自离散化。

代码

constexpr int N = 2e6+5;
constexpr db eps = 1e-6;

db raw[N];
int num = 0,c;
inline void add_num(db x){++num,raw[num] = x;}
inline int id(db x){return lower_bound(raw+1,raw+1+c,x)-raw;}
inline void discrete(){
    sort(raw+1,raw+1+num);
    c = unique(raw+1,raw+1+num)-raw-1;
}

int n,x[N],cf[N],sum[N];

inline void add(int l,int r,int v){cf[l]+=v,cf[r+1]-=v;}

void solve(){
    read(n);
    cout<<fixed<<setprecision(7);
    for(int i=1;i<=n;i++){
        read(x[i]);
        db l,r;
        for(int j=1;j<=x[i];j++){
            l = (db)x[i]/j,r = (db)(x[i]+1)/j;
            add_num(l+eps),add_num(r);
        }
    }
    discrete();
    for(int i=1;i<=n;i++){
        int l,r;
        for(int j=1;j<=x[i];j++){
            l = id(((db)x[i]/j)+eps),r = id((db)(x[i]+1)/j);
            add(l,r,1);
        }
        for(int j=1;j<=c;j++)	cf[j]+=cf[j-1];
        cf[0] = 0;
        for(int j=1;j<=c;j++){
            sum[j]+=(bool)cf[j];
            cf[j] = 0;
        }
    }
    for(int j=c;j>=1;j--){
        if(sum[j]==n){cout<<raw[j];return;}
    }
    cout<<1.000000;
}