题解：奶牛位置调整问题

题目分析

本题要求将奶牛排列在长度为$L+1$的直线上，使得相邻奶牛之间的距离尽可能均匀（只能为$D$或$D+1$），并计算最小移动时间。关键在于确定合理的目标位置，使得总移动距离最小。

解题思路

1. 确定平均间隔：
   总间隔数为$N-1$，平均间隔$D = \lfloor \frac{L}{N-1} \rfloor$。
   余数$R = L \mod (N-1)$，表示有$R$个间隔需要为$D+1$，其余为$D$。

2. 动态规划预处理左右边界：

   • l[i]：第$i$头奶牛可放置的最小位置。
   • r[i]：第$i$头奶牛可放置的最大位置。
     这些边界由平均间隔和余数决定，确保总长度不超过$L$。

3. 动态规划求解最小移动时间：

   • 状态定义：f[j]表示前$i$头奶牛放置在位置$j$时的最小移动时间。
   • 状态转移：遍历所有可能的位置$j$，并从前驱状态（$j-D$或$j-D-1$）转移而来。

代码解释

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,d,L,a[100500],f[100500],l[100500],r[100500];
int main(){
    scanf("%d%d",&n,&L);
    d=L/(n-1);  // 计算平均间隔D
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        // 计算第i头奶牛可放置的最小位置
        l[i]=max(i*d,L-(n-i-1)*(d+1));
        // 计算第i头奶牛可放置的最大位置
        r[i]=min((i+1)*(d+1),L-(n-i-1)*d);
    }
    memset(f,0x3f,sizeof(f));  // 初始化为无穷大
    f[0]=a[0];  // 第1头奶牛必须放在位置0
    for(int i=1;i<n;i++){
        for(int j=r[i];j>=l[i];j--){
            int temp=0x3ffffff;  // 临时变量，存储前驱状态的最小值
            // 检查j-D是否在前驱奶牛的合法范围内
            if(j-d>=l[i-1]&&j-d<=r[i-1])temp=f[j-d];
            // 检查j-D-1是否在前驱奶牛的合法范围内
            if(j-d-1>=l[i-1]&&j-d-1<=r[i-1])temp=min(temp,f[j-d-1]);
            // 更新当前状态
            f[j]=temp+abs(j-a[i]);
        }
    }
    printf("%d\n",f[L]);  // 输出最后一头奶牛在位置L时的最小移动时间
}

关键步骤解析

1. 计算平均间隔和余数：
   $D = \lfloor \frac{L}{N-1} \rfloor$，确定基础间隔。

2. 预处理左右边界：

   • l[i]确保前$i$头奶牛的最小总间隔不小于$i \times D$。
   • r[i]确保后$N-i-1$头奶牛的最大总间隔不超过$(N-i-1) \times (D+1)$。

3. 动态规划状态转移：

   • 对于每头奶牛$i$，遍历其合法位置$j$。
   • 从前驱状态$j-D$或$j-D-1$转移，取最小值并加上当前位置的移动距离。

4. 结果输出：
   最终答案为$f[L]$，即最后一头奶牛放置在位置$L$时的最小移动时间。

复杂度分析

• 时间复杂度：$O(N \times D)$，其中$D$为平均间隔。
• 空间复杂度：$O(N)$，主要用于存储动态规划数组和边界数组。

该算法通过合理的预处理和动态规划，确保在满足约束条件下找到最小移动时间，有效解决了奶牛位置调整问题。