令 \(p_0=0,m\leftarrow m+1,p_{m}=n,a_i=p_i-p_{i-1}\)，设在 \((p_{i-1},p_i)\) 中有 \(d_i-1\) 个 B 变成了 A，满足 \(\sum_{i=1}^m(d_i-1)=k\)，让 \(k\leftarrow k+m\)，这样 \(d\) 需要满足的限制就变成了 \(\sum_{i=1}^m d_i=k\)。这也可以看作把 \(a_i\) 分成 \(d_i\) 个正整数之和，每个正整数代表相邻两个 A 的距离，我们要最小化最后划分出来的正整数的极差。
可以发现每一段非负整数划分得越平均越好，所以每一段一定都是划分成若干个 \(\lfloor\frac{a_i}{d_i}\rfloor\) 和若干个 \(\lceil\frac{a_i}{d_i}\rceil\)，我们要最小化的东西就是 \(\max_{i=1}^m\lceil\frac{a_i}{d_i}\rceil\le R-\min_{i=1}^m\lfloor\frac{a_i}{d_i}\rfloor\)。
现在给定 \((L,R)\)，我们要判断是否存在 \(d_i\) 满足 \(\sum_{i=1}^m d_i=k,\max_{i=1}^m\lceil\frac{a_i}{d_i}\rceil\le R,\min_{i=1}^m\lfloor\frac{a_i}{d_i}\rfloor\ge L\)，即每个被划分出的正整数都要在 \([L,R]\) 内，如果存在的话我们把 \(R-L\) 计入答案。注意 \(R-L\) 可能是大于此时的极差的，但这不会使最终答案变小，同时最优答案也一定会被统计到，所以不影响最终答案。
首先 \(d_i\ge\lfloor\frac{a_i}{L}\rfloor\)，即记 \(t_L=\lfloor\frac{a_i}{L}\rfloor\)，那么有 \(t_LL\le a_i,(t_L+1)L\gt a_i\)，如果 \(t_LR\lt a_i\) 那就无解了，否则 \(t_LR\ge a_i\)，由于 \(t_LL\le a_i\le t_LR\)，所以我们可以把 \(a_i\) 分成 \(t_L\) 个 \([L,R]\) 内的正整数（且至多只能划分出 \(t_L\) 个）。
同理，通过 \(d_i\le\lceil\frac{a_i}{R}\rceil\) 也可以说明，记 \(t_R=\lceil\frac{a_i}{R}\rceil\)，如果 \(t_RL>a_i\) 则无解，否则我们也一样可以把 \(a_i\) 分成 \(t_R\) 个 \([L,R]\) 内的正整数（且至少要划分出 \(t_R\) 个）。
由于 \(t_LL\le a_i\le t_LR\)，\(t_RL\le a_i\le t_RR\)，那么对于 \(t_R\le t\le t_L\) 也都有 \(tL\le a_i\le tR\)，于是我们能且仅能把 \(a_i\) 分成 \(t\in[t_R,t_L]\) 个 \([L,R]\) 内的正整数。
我们再研究一下判有无解的式子，\(t_LR\ge a_i,t_RL\le a_i\)，对于前者，代入 \(t_L=\lfloor\frac{a_i}{L}\rfloor\) 得 \(\lfloor\frac{a_i}{L}\rfloor R\ge a_i\Leftrightarrow \lfloor\frac{a_i}{L}\rfloor \ge\frac{a_i}{R}\Leftrightarrow \lfloor\frac{a_i}{L}\rfloor \ge \lceil\frac{a_i}{R}\rceil\)，对于后者我们能推出同样的式子。
把 \(m\) 段综合一下，充要条件就是：1. \(\sum_{i=1}^m\lceil\frac{a_i}{R}\rceil\le k\le\sum_{i=1}^m\lfloor\frac{a_i}{L}\rfloor\)；2. \(\forall 1\le i\le m,\lfloor\frac{a_i}{L}\rfloor \ge \lceil\frac{a_i}{R}\rceil\)。
对于第一个条件，\(L\) 有上限，\(R\) 有下限，可以二分求出 \(L\) 的上限 \(L_0\)，\(R\) 的下限 \(R_0\)，那么第一个条件成立当且仅当 \(L\le L_0\) 且 \(R\ge R_0\)，所以答案至少为 \(R_0-L_0\)。
对于第二个条件，由于 \(L\le R\)，所以 \(\frac{a_i}{L}\ge\frac{a_i}{R}\)，那么不满足第二个条件时一定有 \(\lceil\frac{a_i}{R}\rceil=\lfloor\frac{a_i}{L}\rfloor+1\)。
如果没有不满足第二个条件的 \(a_i\)，那么答案就是 \(R_0-L_0\)。
否则，我们希望通过调小 \(L\) 或调大 \(R\) 使得 \(\lfloor\frac{a_i}{L}\rfloor \ge \lceil\frac{a_i}{R}\rceil\) 成立，这等价于存在整数 \(x\)，满足 \(\lfloor\frac{a_i}{L}\rfloor \ge x\ge \lceil\frac{a_i}{R}\rceil\)，对于不等式前半部分 \(\lfloor\frac{a_i}{L}\rfloor \ge x\Leftrightarrow\frac{a_i}{L}\ge x\Leftrightarrow \frac{a_i}{x}\ge L\Leftrightarrow \lfloor\frac{a_i}{x}\rfloor\ge L\)，不等式后半部分等价于 \(\lceil\frac{a_i}{x}\rceil\le R\)，综合两式得到我们希望存在整数 \(x\) 使得 \(L\le\lfloor\frac{a_i}{x}\rfloor\le\lceil\frac{a_i}{x}\rceil\le R\)。
显然，我们希望 \(\lfloor\frac{a_i}{x}\rfloor\) 比 \(L\) 大且最接近 \(L\)，或者 \(\lceil\frac{a_i}{x}\rceil\) 比 \(R\) 小且尽量接近 \(R\)。对于前者应让 \(x=\lfloor\frac{a_i}{L}\rfloor\)，但由于现在不存在 \(x\) 满足上述条件，所以 \(\lceil\frac{a_i}{x}\rceil>R\)，但我们发现 \(\lceil\frac{a_i}{x+1}\rceil\le R\)，所以我们可以把 \(L\) 缩小到 \(\lfloor\frac{a_i}{x+1}\rfloor\)；同理也可以把 \(R\) 扩大到 \(\lceil\frac{a_i}{\lceil\frac{a_i}{R}\rceil-1}\rceil\)。同时根据如上论述我们发现只需要把 \(L,R\) 其一缩小或扩大即可，而不需要同时改变两者。
也就是说，对于每个不满足条件的 \(a_i\)，我们可以求出一个二元组 \((L_i,R_i)\)，我们可以将 \(L\) 缩小为 \(L_i\)，\(R\) 不变，或者将 \(R\) 扩大为 \(R_i\)，\(L\) 不变。现在你有很多对二元组，你要在每个二元组中选一个元素，并修改对应的 \(L,R\)，希望最终得到的 \(R-L\) 最小。这是一个很经典的问题，做法是把二元组按第一维排序，容易证明选 \(L_i\) 的二元组一定是一段后缀。
总时间复杂度 \(O(m\log n)\)。
Code
#include<bits/stdc++.h>
#define LL long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int MxN=400002;
LL n,k,l,r,mid,res,L,R,ans;
int m,Test_num;
LL a[MxN];
typedef pair<LL,LL> P;
vector<P> vec;
template<class T>void read(T &x)
{
x=0;int f=0;char ch=getchar();
while(ch<'0' || ch>'9')f|=(ch=='-'),ch=getchar();
while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
x=f? -x:x;return ;
}
inline void solve()
{
read(n),read(m),read(k),vec.clear(),ans=inf;
for(int i=1;i<=m;++i)read(a[i]);
a[0]=0,a[++m]=n,k+=m;
for(int i=m;i;--i)a[i]-=a[i-1];
for(l=1,r=n;l<=r;)
{
mid=((l+r)>>1),res=0;
for(int i=1;i<=m;++i)res+=(a[i]+mid-1)/mid;
if(res<=k)r=mid-1;
else l=mid+1;
}
R=l;
for(l=1,r=n;l<=r;)
{
mid=((l+r)>>1),res=0;
for(int i=1;i<=m;++i)res+=a[i]/mid;
if(res>=k)l=mid+1;
else r=mid-1;
}
L=r;
for(int i=1;i<=m;++i)
{
LL x=a[i]/L,y=(a[i]+R-1)/R;
if(x<y)vec.push_back(P(a[i]/(x+1),y>1? (a[i]+y-2)/(y-1):inf));
}
if(!vec.size())return (void)(printf("%lld\n",R-L));
sort(vec.begin(),vec.end()),res=-inf;
for(int i=0;i<vec.size();++i)ans=min(ans,max(R,res)-min(L,vec[i].first)),res=max(res,vec[i].second);
ans=min(ans,max(R,res)-L),printf("%lld\n",ans);
}
int main()
{
for(read(Test_num);Test_num--;)solve();
return 0;
}