D2. Chopping Carrots (Hard Version) （每日一题）

D2. Chopping Carrots (Hard Version)

题意：给定一个长度为n的数组a，要你拟定一个长度为n的数组p，使得下列公式求得的值最小

做法：固定最小值，考虑枚举使得最大值最小化，利用整除分块的思想，ai/pi的整除值实际上只有sqrt(ai)个，n*sqrt(n)的复杂度可以接受。

我们设max[i]数组，其意义为：a[i]/p[i]最小值为i时的最大值为多少（考虑多个ai的情况就能明白了），对于每个a[i]都要枚举。
假如现在的这个区间是[]

对于代码中maxx数组的更新，模拟一下便于理解
比如基值是100 第一段区间是（51，100]，那么最小值是51的情况下我至少得是100
下面是代码的模拟。
比如此时ai是100
第一次temp=100
r=1
maxx[100+1]=无穷大
pv=100

第二次
temp=50
r=2
maxx[50+1]=max(maxx[50+1]，100)

第三次
temp=33
r=3

#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int MAXN = 100100;
int t,n,k,a[MAXN],maxx[MAXN];
int main()
{
    
    for(cin>>t;t;t--)
    {
    
        cin>>n>>k;
        memset(maxx,0,sizeof(maxx));
        for(int i=0;i<n;i++)
        {
    
            cin>>a[i];
            int pv=1e9;
            for(int j=1,r,temp;j<=min(a[i],k);j=r+1)
            {
    
                temp=a[i]/j;
                r=a[i]/temp;//整除分块的思想

                maxx[temp+1]=max(maxx[temp+1],pv);//由于整除分块是的值是递减的，所以上一个值一定比现在的大
                pv=temp;
            }
            maxx[0]=max(maxx[0],pv);
        }
        int ans=1e9;
        int cm=0;
        for(int i=0;i<=a[0];i++)
        {
    
            cm=max(cm,maxx[i]);
            ans=min(ans,cm-i);
        }
        cout<<ans<<"\n";
    }
    return 0;
}