小红的项链

[编程题]小红的项链

热度指数：732 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红将 $n$ 个珠子排成一排，然后将它们串起来，连接成了一串项链（连接后为一个环，即第一个和最后一个珠子也是相邻的），任意相邻两个珠子的距离为1。已知初始共有3个珠子是红色的，其余珠子是白色的。

小红拥有无穷的魔力，她可以对项链上的相邻两个珠子进行交换。小红希望用最小的交换次数，使得任意两个红色的珠子的最小距离不小于 $k$ ，你能帮小红求出最小的交换次数吗？

输入描述:

第一行输入一个正整数，代表询问次数。
每行为一次询问，输出五个正整数，分别代表珠子总数量、要求的珠子距离，以及三个珠子的位置。



保证互不相同。

输出描述:

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

示例1

输入

2
6 2 1 2 3
5 2 1 3 4

输出

2
-1

说明

第一组样例，六个珠子为红红红白白白。第一次操作交换第一个和第六个珠子，第二次操作交换第三个和第四个珠子。
第二组询问，一共有5个珠子，其中有3个红珠子，因此无论如何都会有两个红珠子相邻，不可能满足任意两个红珠子的最小距离不小于2。

算法知识视频讲解

牛客549748438号

3 * k会超int，记得转long

发表于 2025-08-08 17:31:44 回复(0)

Miluko

fun getCycledDistance(a: Int, b: Int, n: Int): Int {
    val distance = abs(b - a)
    return min(distance, n - distance)
}

fun solve(n: Int, k: Int, a: Int, b: Int, c: Int): Long {
    if (n < 3 * k) return -1
    val points = mutableListOf(a, b, c)
    points.sort()
    val arcs = mutableListOf(
        getCycledDistance(points[0], points[1], n),
        getCycledDistance(points[0], points[2], n),
        getCycledDistance(points[1], points[2], n)
    )
    if(false !in arcs.map { it >= k }) return 0
    arcs.sort()
    return Math.max(0, k - arcs[0]) + Math.max(0, k - arcs[1])
}

使用补全弧长法可以很快解题：

当 n < 3k 时，必定无法达到目标，直接返回 -1

然后检查当前形成的所有弧，如果都符合条件，即不需要调整，直接返回0

剩下的情况，已知对于A = { arc[0], arc[1], arc[2] }，Sum(A) > 3k，且存在 x ∈ A 使得 x < k；则必定有max(A) > k，这时可以认定对于剩下的两个点，共计需要移动 max(0, k -arc[i]) 的长度（k - arc[i] < 0 时：满足条件，不需要进行移动，故取0）；

发表于 2025-11-04 10:36:08 回复(0)

凤溪小阁

#include <iostream>
using namespace std;

void sort(int &a1,int &a2,int &a3){
    int t;
    if(a1<a2&&a2<a3){
        return ;
    }
    if(a1>a2){
        t=a1,a1=a2,a2=t;
    }
    if(a1>a3){
        t=a1,a1=a3,a3=t;
    }
    if(a2>a3){
        t=a2,a2=a3,a3=t;
    }
}

int main() {
    int t;
    cin>>t;
    for(int i=0;i<t;i++){
        int n,k,a1,a2,a3;
        cin>>n>>k>>a1>>a2>>a3;
        if(n/3<k){
            cout<<"-1"<<endl;
            continue;
        }
        else{
            sort(a1,a2,a3);
            int a12,a13,a23;
            a12=a2-a1;
            a23=a3-a2;
            a13=n-a3+a1;
            int t1=a12,t2=a23,t3=a13;
            sort(t1,t2,t3);
            cout<<max(0,k-t1)+max(0,k-t2)<<endl;
        }
    }
}

发表于 2025-08-23 22:13:08 回复(0)