自动搬运

查看原文

来自洛谷，原作者为

	Laisira 初中数学考得跟小学数学一个逼分的废物

搬运于2025-08-24 23:00:12，当前版本为作者最后更新于2024-07-01 14:39:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面

定义一个实数 $\alpha$ 的谱 $\operatorname{Spec}(\alpha)$ 是整数组成的一个无限长的序列 $\lceil\alpha\rceil-1,\lceil2\alpha\rceil-1,\lceil3\alpha\rceil-1,\cdots$。例如，$\frac35$ 的谱的开头部分是 $0,1,1,2,2,3,4,\cdots$。

现在给定 $n$ 个整数 $x_1,\cdots,x_n$，你要找到最大的实数 $\alpha$，使得对于每个元素 $x_i$ 都有 $x_i$ 在 $\operatorname{Spec}(\alpha)$ 中出现过。

思路

这题暴力啊！

我们设 $u$ 使得 $\alpha \times u-1\leq x_{Max}$。我们暴力枚举 $\alpha$ 的范围只是 $(0,(x_{Max}-1)/u]$，每次要枚举 $\max(u,n)$ 次，时间复杂度是 $x_{Max}-1$，也就是差不多 $10^3$。再算上精确到 $10^5$，即 $\alpha$ 总共最坏时间复杂度是 $10^9$。

这时我们发现我们并不知道 $(0,(x_{Max}-1)/u]$ 是啥，但我们可以估计到一点，即 $u>m$，$m$ 指种数。我们至少枚出 $m$ 种数，于是稳过。

（话说赛后我给一个同学讲我的解法，Ta 说 Ta 气炸了。）

update：发现可以小小的优化。

代码

#include<bits/stdc++.h>
using namespace std;
int a[10000];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n);
    n=unique(a+1,a+1+n)-a-1;
    double opt=double(a[n]+1)/n;
    for(;opt>=0;opt-=0.00000100) {
        int r=1,l=1;
        while((int)(ceil(opt*r*1.0000000)-1)<=a[l]&&l<=n) {
            if((int)(ceil(opt*r*1.0000000)-1)==a[l])l++;
            r++;
        } if(l>n) {
            printf("%.7f",opt);
            return 0;
        }
    }
    return 0;
}