题解：P17299 [ICPC 2026 Xi'an I] Split Sticks

· · 题解

题意简述

给定一排木棍。 每次选择一根木棍，把它切成两个整数长度的部分， 再分别并入左右相邻木棍。 位于端点时，没有相邻木棍的一段独立保留。

求最少需要多少次操作，才能使剩余木棍全部等长。

解题思路

把所有木棍首尾相接，放在线段 [0,S] 上。 设初始分界点为：

0=p_0<p_1<\dots<p_n=S

对一根内部木棍操作时， 它两侧的相邻分界点会合并为两点之间的任意整数点。 也就是说，两个相邻的内部分界点减少为一个。

对首端木棍操作时， 可以把最左侧的内部分界点移动到它与 0 之间； 尾端的情况关于 S 对称。

设最后剩下 m 根木棍。 总长度始终为 S，所以必须满足 m\mid S。 此时每根木棍的长度和最终分界点已经唯一确定：

\begin{aligned} x & =\frac{S}{m} \\ q_i & =ix \end{aligned}

其中 1\leq i<m。

若只使用内部操作， 每个最终分界点都由一段非空、连续的初始内部分界点合并而成。 一组分界点可以合并到其最左与最右位置之间的任意整数点。

考虑相邻的最终分界点 q_i 与 q_{i+1}。 它们对应的两组初始分界点之间， 一定存在一对相邻分界点 p_j,p_{j+1}。 左组能够合并到 q_i，需要 p_j\geq q_i； 右组能够合并到 q_{i+1}，需要 p_{j+1}\leq q_{i+1}。 因此必须满足：

ix\leq p_j<p_{j+1}\leq(i+1)x

反过来，若对每个 1\leq i\leq m-2 都能依次找到这样一对分界点， 这些位置就把所有初始内部分界点划分成连续组。 每个中间目标都位于对应组的覆盖范围内， 所以逐组进行相邻合并即可得到所有中间目标。

上述条件可以贪心检查。 从左到右处理区间 [ix,(i+1)x]， 跳过所有满足 p_j<ix 的位置， 取第一个满足 p_j\geq ix 的位置。 若此时 p_{j+1}>(i+1)x， 后续分界点只会更靠右，不可能再满足当前区间。 否则选择这对分界点一定不会妨碍后面的区间。

还需处理首尾两个最终分界点。 若 p_1>x，目标 x 位于所有初始内部分界点左侧， 必须额外操作一次首端木棍，把最左分界点移动到 x。 若 S-p_{n-1}>x，尾端同理需要额外操作一次。

初始有 n-1 个内部分界点，最终有 m-1 个。 每次内部操作只会减少一个分界点， 因此至少需要 n-m 次内部操作。 上面的连续分组构造恰好在每组内合并到只剩一个分界点， 总共也使用 n-m 次。

所以固定 m 时，若中间区间检查通过，答案为：

n-m+[p_1>x]+[S-p_{n-1}>x]

其中 [P] 在命题 P 成立时为 1，否则为 0。

从 m=n 开始递减枚举。 代码改为枚举必需的内部操作数 d=n-m。 若 d 已经不小于当前答案，后续候选不可能更优， 可以直接停止。 只有 m\mid S 时才进行线性检查。

设 \tau(S) 为 S 的约数个数。 时间复杂度为 O(n\tau(S))，空间复杂度为 O(n)。

参考代码

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

using ll=long long;
const int N=1000005;
ll a[N];
bool check(int n,int m,ll x)
{
    if(m<=2)return 1;
    int need=1;
    for(int i=1;i<n&&need<=m-2;i++)
    {
        if(a[i]<need*x)continue;
        if(a[i+1]>(need+1)*x)return 0;
        need++;
    }
    return need==m-1;
}
void solve()
{
    int n;
    cin>>n;
    a[0]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]+=a[i-1];
    }
    int ans=n-1;
    for(int i=0;i<ans;i++)
    {
        int m=n-i;
        if(a[n]%m)continue;
        ll x=a[n]/m;
        int res=i+(a[1]>x)+(a[n]-a[n-1]>x);
        if(res<ans&&check(n,m,x))ans=res;
    }
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}