CF1706D Chopping Carrots

题意

给定一个长度为 $n$ 的不严格递增数列 $a_1,a_2,…,a_n$ 和一个整数 $k$。

对于一个数列 $p_1,p_2,…,p_n$，定义其 cost 等于：
$$
\mathop{max}\limits_{1 \le i \le n} (\lfloor \frac{a_i}{p_i} \rfloor) - \mathop{min}\limits_{1 \le i \le n} (\lfloor \frac{a_i}{p_i} \rfloor)
$$
求对于任意数据范围内的数列 $p$，所能得到的最小 cost。

数据范围：

Easy Version：$1 \le t \le 100(test\ case), 1 \le n,k \le 3000, 1 \le a_1 \le a_2 \le … \le a_n \le 3000$

Hard Version：$1 \le t \le 100(test\ case), 1 \le n,k \le 3000, 1 \le a_1 \le a_2 \le … \le a_n \le 3000$

已知结论

$\lfloor \frac{A}{X} \rfloor \ge B \Leftrightarrow \frac{A}{X} \ge B \Leftrightarrow \frac{A}{B} \ge X \Leftrightarrow \lfloor \frac{A}{B} \rfloor \ge X$

思路

Easy Version

设 $mi = \mathop{min}\limits_{1 \le i \le n} (\lfloor \frac{a_i}{p_i} \rfloor)$，枚举 $mi$，由于数列中的最小值为 $a_1$，故 $0 \le mi \le a_1$；
遍历 $a_1,a_2,…,a_n$，要在满足 $\lfloor \frac{a_i}{p_i} \rfloor \ge mi$ 的前提下使得 $p_i$ 尽可能大，这样 $\mathop{max}\limits_{1 \le i \le n} (\lfloor \frac{a_i}{p_i} \rfloor)$ 会尽可能小。根据结论 1 可知：$p_i$ 的最大值是 $\lfloor \frac{a_i}{mi} \rfloor$（$A$ 代入 $a_i$，$B$ 代入 $mi$，$X$ 代入 $p_i$）；
如此 $O(a_1n)$ 遍历即可得出答案。

代码

Easy Version

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5+5;
 
int a[MAXN];
int main(){
    // freopen("in.txt", "r", stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        int ans=100000;
        if(a[1]/k==0){
            ans=min(ans,a[n]/k);
        }
        for(int mi=1;mi<=a[1];mi++){
            bool flag=0;
            int tm=0;
            for(int i=1;i<=n;i++){
                int p=min(a[i]/mi,k);
                if(a[i]/p==mi)
                    flag=true;
                tm=max(tm,a[i]/p);
            }
            if(flag)
                ans=min(ans,tm-mi);
        }
        printf("%d\n",ans);
    }
 
    return 0;
}