「数论分块」Codeforces Round #809 (Div. 2) D. Chopping Carrots Solution

题面传送门

题意：给定数组a，构造一个数组p，求min\{ max_{1≤i≤n}(⌊\frac{a_i}{p_i}⌋)−min_{1≤i≤n}(⌊\frac{a_i}{p_i}⌋) \}

考虑对于每一个\frac{a_i}{x}，根据数论分块可知，最多有\sqrt{n}个取值。

记f[i]表示最小值为i时的可能最优max。

数论分块时\frac{a_i}{x}逐渐减小，假设数论分块上一个整除出的数为y，当前为x，那么a_i整除出的y可以更新的f就是[x+1,y]。 ①

得到f以后，枚举最小值，然后取f[i]-i的最小值即可。

但是如果直接更新f数组，其实会需要一个log的复杂度，用线段树或者堆也好。

其实每一个a_i在数论分块时的\frac{a_i}{x}不断减小，所以我们可以只更新f[x+1]的值，然后枚举答案时取前缀max即可。

就如上①处，x更新的f在取max时并不会对y更新的f造成影响。

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+70;

int T,n,k,a[N],R,f[N];

int main()
{
    for(scanf("%d",&T);T;--T){
        scanf("%d%d",&n,&k);
        R=0;
        for(int i=1;i<=n;++i)scanf("%d",&a[i]),R=max(R,a[i]);
        int ans=N;
        for(int i=1;i<=n;++i){
            int lst=N;
            for(int l=1,r;l<=a[i]&&l<=k;l=r+1){
                r=a[i]/(a[i]/l);
                f[a[i]/l+1]=max(f[a[i]/l+1],lst);
                lst=a[i]/l;
            }
            f[1]=max(f[1],lst);
        }
        for(int i=1,tmp=0;i<=R;++i)tmp=max(tmp,f[i]),ans=min(ans,tmp-i);
        for(int i=1;i<=R+50;++i)f[i]=0;
        printf("%d\n",ans);
    }
}