小红的项链

[编程题]小红的项链

热度指数：345 时间限制：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。

算法知识视频讲解

凤溪小阁

#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)