受到杨超度同学思路的启发，我觉得这道题可以这样想，需要一个先验知识：X轴上有N个点，求X轴上一点使它到这N个点的距离之和最小。那么根据中位数性质，这个点一定是这组数中的中位数（该性质的简单证明可以参考https://blog.csdn.net/sm_545/article/details/78196351）。

这道题在先验知识的基础上有两个变形，首先题目要求是环，那么我们就在这N个数后面再补上N个数（其中新加的N个数分别是前N个数加环的长度L）然后我们从中截取N段，使得每段都包含了所有的数，分别对每段应用先验知识；其次题目要求移动到相邻位置，那就在先验知识的基础上减去一个常数即可。因为一旦N给定，这个常数就确定了（具体求法见下方代码）

public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int result = Integer.MAX_VALUE;
    int L = sc.nextInt();  //项链的长度
    int N = sc.nextInt();  //珍珠的个数
    int[] nums = new int[2*N+1];  //存拓展后的珍珠位置编号
    int m, constant = 0;
    m = (N+1) / 2;
    for(int i = 1; i <= N ; i++){
        nums[i] = sc.nextInt();
        constant += Math.abs(m - i);  //求先验知识和本题差的那个常数
    }
    Arrays.sort(nums, 1, N+1);  //排序前N个数
    for(int i = N+1; i <=2*N; i++) {
        nums[i] = nums[i - N] + L;  //拓展，补上N个数
    }
    for(int left = 1; left <= N; left++){  //截取N段，每段包含了所有的珍珠
        int answer = 0;  //按照先验知识求的距离和
        int right = left + N-1;
        int i = left, j = right;
        while(i <= j){
            answer += nums[j--] - nums[i++];
        }
        result = Math.min(answer - constant, result);
    }
    System.out.println(result);
}

创作者周榜