思路

题意化简

由于我们只关注相邻点的距离。所以可以先对这些点排个序，然后算出一个相邻距离的数组$b_1,b_2,b_3$

考虑一次交换操作，等价于对这个距离数组的某一个下标:$i$ 以及它的下一个点$(i+1)\%3$ 一个加一个减。

最终目标： 使得$b_1,b_2,b_3 \geq k$ .

做法

显然我们要让小的往上加1，直到其大于等于k。

那么自然的，同时要让大的往下减1。

但是注意我们不要模拟这个过程，而是可以$O(1)$的计算出每个数到k还需要多少次。加起来即可。

代码

java

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int t;
        t = sc.nextInt();

        while (t-- > 0) {
            long n = sc.nextLong();
            long k = sc.nextLong();
            long[] a = new long[3];

            // 读入三个位置
            for (int i = 0; i < 3; i++) {
                a[i] = sc.nextInt();
            }
            // 排序位置a数组
            Arrays.sort(a);
            // 如果需要的k值超过了总距离n的三倍，则无法满足要求，输出-1
            if (k * 3 > n) {
                System.out.println(-1);
                continue;
            }
            // 根据位置数组a求距离数组b
            long[] b = new long[] {a[1] - a[0], a[2] - a[1], n - a[2] + a[0]};
            long ans = 0;
	        // 计算每个相邻距离与k的差值，并求和
            // 注意大于等于k的不用管。最终一定会有解
            for (int i = 0; i < b.length; i++) {
                ans += Math.max(0, k - b[i]);
            }
            System.out.println(ans);
        }
    }
}

python

t = int(input())  # 读入测试用例的数量
for _ in range(t):
    arr = list(map(int, input().split()))  
    n = arr[0] # 读入总距离n和给定值k
    k = arr[1]
    a = arr[2:] # 位置数组a
    a.sort()  # 排序位置a数组
    # 如果需要的k值超过了总距离n的三倍，则无法满足要求，输出-1
    if k * 3 > n:
        print(-1)
        continue
    # 根据位置数组a求距离数组b
    b = [a[1] - a[0], a[2] - a[1], n - a[2] + a[0]]
    ans = 0
    # 计算每个相邻距离与k的差值，并求和
    # 注意大于等于k的不用管。最终一定会有解
    for i in range(len(b)):
        ans += max(0, k - b[i])
    print(ans)

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int t;
    cin >> t;  // 读入测试用例的数量
    while (t--) {
        int n, k;
        cin >> n >> k;  // 读入总距离n和给定值k
        vector<int> a(3);
        for (int i = 0; i < 3; i++) {
            cin >> a[i];  // 读入三个位置
        }
        sort(a.begin(), a.end());  // 排序位置a数组
        // 如果需要的k值超过了总距离n的三倍，则无法满足要求，输出-1
        if (k * 3 > n) {
            cout << -1 << endl;
            continue;
        }
        // 根据位置数组a求距离数组b
        vector<int> b = {a[1] - a[0], a[2] - a[1], n - a[2] + a[0]};
        int ans = 0;
        // 计算每个相邻距离与k的差值，并求和
        // 注意大于等于k的不用管。最终一定会有解
        for (int i = 0; i < b.size(); i++) {
            ans += max(0, k - b[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

题目内容

小红有一个纯白的环形纸带（首尾相连）。这个纸带被划分成n个格子。最开始，小红在纸带上选择了三个格子，把它染黑。

现在小红让你把他们通过移动操作把纸带变成平衡状态。

平衡状态：任意两个黑色格子的距离不小于$k$ (相邻格子距离为1)

移动操作:交换相邻格子的颜色。

同时，小红是一个很注重效率的人，所以他希望你使用最少的移动次数使得纸带达到平衡。

输入描述

第一行输入一个正整数$t$，代表询问次数。

每行为一次询问，输出五个正整数$n,k,a_1,a_2,a_3$，分别代表纸带的格子数、要求的距离，以及三个黑色格子的初始位置。

$1 \leq t \leq 10^4$

$1 \leq n \leq 10^9$

$1 \leq k,a_1,a_2,a_3 \leq n$

输出描述

输出$t$行，每行输入一个整数，代表最小的交换次数。如果无法完成目的，则输出$-1$。

样例

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

3
5 1 1 2 3
5 2 1 2 3
6 2 2 3 6

输出

0
-1
1

说明

第一组样例，无需交换即可满足任意两个黑色格子的距离为1,输出0

第二组样例，由于相隔为2的情况下至少需要6个格子，则5个格子无论如何无法满足条件，输出-1

第三组样例，状态为:白黑黑白白黑。我们只需要交换一次变成白黑白黑白黑即可满足条件。输出1