D2. picking carrots (hard version) (one question per day)

D2. Chopping Carrots (Hard Version)

The question ： Given a length of n Array of a, I want you to draw up a length of n Array of p, Minimize the value obtained by the following formula

practice ： Fixed minimum , Consider enumerations to minimize the maximum , Using the idea of dividing into blocks ,ai/pi The integer division value of is actually only sqrt(ai) individual ,n*sqrt(n) The complexity is acceptable .

We set up max[i] Array , Its significance is ：a[i]/p[i] The minimum value is i What is the maximum value of （ Consider multiple ai You can understand the situation ）, For each a[i] All have to enumerate .
Suppose the current interval is []

For code maxx Array update , Simulate it for understanding
For example, the base value is 100 The first interval is （51,100], Then the minimum value is 51 In this case, I have to at least 100
The following is the code simulation .
For example, at this time ai yes 100
for the first time temp=100
r=1
maxx[100+1]= infinity
pv=100

The second time
temp=50
r=2
maxx[50+1]=max(maxx[50+1],100)

third time
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;// The idea of dividing into blocks 

                maxx[temp+1]=max(maxx[temp+1],pv);// Because the value of dividing blocks is decreasing , So the previous value must be larger than the current one 
                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;
}