题解：P10679 『STA - R6』spec

Laisira · 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;
}