题解 | #小红的项链#

题目链接

小红的项链

题目描述

在一个由 $n$ 个珠子组成的环形项链上，有 3 个红色珠子，其余为白色。任意相邻两个珠子的距离为 1。小红希望通过最少的相邻珠子交换次数，使得任意两个红色珠子之间的最小距离不小于 $k$ 。

任务是计算所需的最小交换次数。如果目标无法达成，则输出 -1。

解题思路

这个问题的核心在于，通过移动珠子来重新分配它们之间的“空位”，使得所有空位长度都大于等于 $k$ ，并且总的移动成本最低。

1. 可行性判断

首先，为了使 3 个红珠子之间的距离都至少为 $k$ ，项链的总长度 $n$ 必须至少为 $3k$ 。如果 $n < 3k$ ，则无论如何都无法满足条件，应输出 -1。

2. 最小交换次数的核心逻辑

移动一个珠子一格，会使其一侧的间距增加 1，另一侧的间距减少 1。这本质上是在相邻的两个“空位段”之间转移了 1 个单位的长度，成本为 1。因此，总的交换次数就等于为了满足条件，所有“空位段”之间需要转移的总长度。

我们可以通过以下步骤找到最优解：

计算初始间距：

首先，将三个珠子的位置 $p_0, p_1, p_2$ 排序。然后计算它们之间的三个弧长（即间距）：
- $d_0 = p_1 - p_0$
- $d_1 = p_2 - p_1$
- $d_2 = n - (p_2 - p_0)$
排序间距：

将这三个间距进行排序，得到 $t_1 \le t_2 \le t_3$ 。
计算成本：

我们的目标是让所有间距都 $\ge k$ 。
- 对于最小的间距 $t_1$ ，如果它小于 $k$ ，则需要增加 $k - t_1$ 的长度。
- 对于次小的间距 $t_2$ ，如果它小于 $k$ ，则需要增加 $k - t_2$ 的长度。
- 最大的间距 $t_3$ 是否有足够的“盈余”长度来填补这两个“亏空”呢？
  - 总“亏空”为 $\max(0, k-t_1) + \max(0, k-t_2)$ 。
  - $t_3$ 的“盈余”为 $\max(0, t_3-k)$ 。
  - 我们可以证明，盈余总是大于等于亏空： $(t_3 - k) - ((k-t_1) + (k-t_2)) = (t_1+t_2+t_3) - 3k = n - 3k \ge 0$ 。
因此，最大的间距 $t_3$ 永远可以作为“供给源”，满足另外两个间距的需求。总的移动成本就等于两个较小间距的总“亏空”。

最终算法：

检查 $n \ge 3k$ ，否则输出 -1。
计算三个间距 $d_0, d_1, d_2$ 。
对三个间距排序，得到 $t_1, t_2, t_3$ 。
答案为 $\max(0, k - t_1) + \max(0, k - t_2)$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

void solve() {
    long long n, k;
    cin >> n >> k;
    vector<long long> p(3);
    cin >> p[0] >> p[1] >> p[2];

    if (n < 3 * k) {
        cout << -1 << endl;
        return;
    }

    sort(p.begin(), p.end());

    vector<long long> d(3);
    d[0] = p[1] - p[0];
    d[1] = p[2] - p[1];
    d[2] = n - (p[2] - p[0]);

    sort(d.begin(), d.end());

    long long cost = 0;
    if (d[0] < k) {
        cost += k - d[0];
    }
    if (d[1] < k) {
        cost += k - d[1];
    }
    
    cout << cost << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.util.Arrays;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }
    
    private static void solve(Scanner sc) {
        long n = sc.nextLong();
        long k = sc.nextLong();
        long[] p = new long[3];
        p[0] = sc.nextLong();
        p[1] = sc.nextLong();
        p[2] = sc.nextLong();

        if (n < 3 * k) {
            System.out.println(-1);
            return;
        }

        Arrays.sort(p);

        long[] d = new long[3];
        d[0] = p[1] - p[0];
        d[1] = p[2] - p[1];
        d[2] = n - (p[2] - p[0]);

        Arrays.sort(d);
        
        long cost = 0;
        if (d[0] < k) {
            cost += k - d[0];
        }
        if (d[1] < k) {
            cost += k - d[1];
        }

        System.out.println(cost);
    }
}

import sys

def solve():
    line = sys.stdin.readline().split()
    n, k = int(line[0]), int(line[1])
    p = sorted([int(line[2]), int(line[3]), int(line[4])])

    if n < 3 * k:
        print(-1)
        return

    d = [0, 0, 0]
    d[0] = p[1] - p[0]
    d[1] = p[2] - p[1]
    d[2] = n - (p[2] - p[0])

    d.sort()
    
    cost = 0
    if d[0] < k:
        cost += k - d[0]
    if d[1] < k:
        cost += k - d[1]
        
    print(cost)

def main():
    try:
        t_str = sys.stdin.readline()
        if not t_str: return
        t = int(t_str)
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        pass

if __name__ == "__main__":
    main()

算法及复杂度

算法：数学、贪心
时间复杂度：对于每次查询，算法只涉及对 3 个元素进行排序和一些基本算术运算。因此，每次查询的时间复杂度为 $\mathcal{O}(1)$ 。
空间复杂度：对于每次查询，我们只需要存储少数几个变量。因此，空间复杂度为 $\mathcal{O}(1)$ 。