题解：P10679 『STA - R6』spec

zibenlun · 2024-06-30 19:59:22 · 题解

极限AC

赛事想出了一个很极限的算法，复杂度十分抽象，只能说拜谢洛谷评测机。

思路

很显然当 α 是 1 的时候，肯定可以得到所有的 x_i ，所以答案肯定大于等于 1 。之后我们通过一点点的思考可以知道，如果 α 比 x_1 大 1 以上的话，一定是不能够得到 x_1 的，所以我们可以求出枚举的范围。之后我们在这个区间上枚举，每 0.000002 枚举一次，并进行检查，就能找到最大的 α 。

CODE

#include<bits/stdc++.h>
#define double long double
using namespace std;
int n,a[100005];

set<int> ss;
bool check(double x){
    for(int i=1;i<=n;i++){
        int l=0,r=1e4,flag=0;
        int ans=1e9;
        while(l<=r){
            int mid=(l+r)>>1;
            if((int)ceil(mid*x)-1<=a[i]){
                l=mid+1;
            }
            else {
                r=mid-1;
                ans=min(ans,mid);   
            }
        }
        for(int j=ans-2;j<=ans+2;j++){
            if((int)ceil(j*x)-1==a[i]){
                flag=1;
                break;
            }
        }
        if(flag==0) return 0;
    }
    return 1;
}
double ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) {
        int x;
        cin>>x;
        ss.insert(x);
    }
    n=0;
    for(auto i:ss){
        a[++n]=i;
    }
    for(double i=a[1]+1;i>=1;i-=0.000002){
        if(check(i)){
            cout<<fixed<<setprecision(7)<<i;
            return 0;
        }
    }
    return 0;
}