题解：P10679 『STA - R6』spec

· · 题解

P10679 『STA - R6』spec 题解

题目传送门

思路

首先我们发现这个减 1 非常不优美，所以我们把所有的 x 加上 1。

接着发现重复的 x 没有什么用，所以我们排序并去重。

这里需要注意到答案一定不小于 1，因为答案为 1 可以覆盖所有的数。

接下来，我们假设每个数都是答案 ans 的 k_i 倍上取整，于是我们枚举 ans\times k_1=x_1 的 k_1，根据上面的结论发现 k_1 不大于 x_1。

然后我们对每个 x_i 进行判断，看 ans 的 k_i 倍上取整能不能覆盖到它，如果不能，直接跳出。

当我们发现一个合法的答案时，它一定是最大的，因为我们的枚举顺序是从大到小的。

而且因为我们枚举了 k_1，所以再去重后的数组中枚举 k_2 可以从 k_1+1 开始枚举，这样可以少很多无用枚举。

代码

#include<bits/stdc++.h>
#define N 1005
#define eps 2e-6
using namespace std;
int n,a[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        a[i]++;
    }
    sort(a,a+n);
    n=unique(a,a+n)-a;//排序并去重
    double res=0;
    for(int i=1;i<a[0];i++){//枚举倍数
        double l=a[0]*1.0/i,r=a[0]*1.0/(i+1);
        for(double j=l;j>r;j-=eps){
            bool flag=1;
            int cnt=i;
            for(int k=0;k<n;k++){
                while(ceil(j*cnt)<a[k])cnt++;//如果仍然小于，就+1
                if(ceil(j*cnt)>a[k]){//cnt-1一定小于，而cnt又大于，所以覆盖不到它1，答案不合法
                    flag=0;
                    break;
                }
            }
            if(flag){
                res=j;//找到答案
                break;
            }
        }
        if(res)break;
    }
    cout<<setiosflags(ios::fixed)<<setprecision(6);
    cout<<res;
    return 0;
}