CF1706D2
hgzxwzf
·
·
题解
解题思路：
D1:
首先预处理出来每个数字 $a_i$ 当 $p\in[1,k]$ 时 $\lfloor \frac{a_i}{p}\rfloor$ 能取到的值。
然后枚举最大值，再用二分找到对于每个 $i$ 的最接近但比枚举到的最大值小的 $\lfloor \frac{a_i}{p}\rfloor$，记为 $w_i$，取所有 $w_i$ 的最小值即可，最后的答案就是最小的最大值减最小值。
#### 代码：
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=z;x>=y;x--)
using namespace std;
const int N=3000+10;
int a[N],te[N][N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(te,0,sizeof(te));
int n,k;
scanf("%d%d",&n,&k);
rep(i,1,n) scanf("%d",&a[i]);
rep(i,1,n)
per(j,1,k)
te[i][++te[i][0]]=a[i]/j;
int ans=1e9;
rep(i,1,3000)
{
bool f=1;
int mmin=1e9;
rep(j,1,n)
{
int pos=upper_bound(te[j]+1,te[j]+1+te[j][0],i)-te[j]-1;
if(pos==0) {f=0;break;}
mmin=min(mmin,te[j][pos]);
}
if(f) ans=min(ans,i-mmin);
}
printf("%d\n",ans);
}
return 0;
}
```
### D2：
$n,k\le100000$，$n^2$ 肯定不太行。
观察到预处理部分可以用数论分块把时间优化到 $O(n\sqrt{n})$。
但如果把所有的 $\lfloor \frac{a_i}{p}\rfloor$ 可能的取值都存下来空间会炸，实际上我们只关心比一个数小的最大数。
对于每个 $i$，首先得到 $\lfloor \frac{a_i}{p}\rfloor$ 可能的取值，记录在 $te$ 中，然后排序，执行：
```cpp
rep(j,1,tot) mx[te[j]]=max(mx[te[j]],te[j+1]);
```
$te_{j+1}$ 就是 $te$ 中比 $tr_j$ 大的最小数，$mx$ 是全局数组。
求答案：
```cpp
rep(i,0,100000)
{
ans=min(ans,mmax-i);
mmax=max(mmax,mx[i]);
}
```
首先 $mmax$ 一定大于等于 $i$，因为 $mmax\ge mx_{i-1}$，而 $mx_{i-1}>i-1$，所以 $mmax\ge i$。
其次 $mmax$ 一定是能取到的大于等于 $i$ 的数中最小的。
#### 代码：
```
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=z;x>=y;x--)
using namespace std;
const int N=1e5+10;
void R(int &x)
{
x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
int a[N],te[N],mx[N];
inline int get(int l,int n)
{
return n/(n/l);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(mx,0,sizeof(mx));
int n,k,mmax=0;
R(n),R(k);
rep(i,1,n) R(a[i]);
rep(i,1,n)
{
int tot=0;
for(int l=1,r=0;l<=min(k,a[i]);l=r+1)
{
r=get(l,a[i]);
te[++tot]=a[i]/l;
}
if(k>a[i]) te[++tot]=0;
reverse(te+1,te+1+tot);
mmax=max(mmax,te[1]);
te[tot+1]=1e9;
rep(j,1,tot) mx[te[j]]=max(mx[te[j]],te[j+1]);
}
int ans=1e9;
rep(i,0,100000)
{
ans=min(ans,mmax-i);
mmax=max(mmax,mx[i]);
}
printf("%d\n",ans);
}
return 0;
}
```