首页 > 试题广场 >

美妙的约会

[编程题]美妙的约会

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

牛牛和妞妞在一天晚上决定一起去看一场情人节演唱会，可是由于这场演唱会实在太出名了，有很多情侣都来观看，牛牛和妞妞不小心被人流冲散了！
维持秩序的人决定，让大家排成一列，相邻两个进去的人（2k-1和2k，k为正整数）坐在相邻座位。但是现在的队伍乱糟糟的，有很多情侣都不在相邻位置。维持秩序的人同意让情侣们跟相邻的人交换位置，直到所有情侣都在2k-1和2k位置上为止。
但是维持秩序的人很没有耐心，所以需要最少的交换次数，你能帮情侣们算出这个次数吗？

输入描述:

第一行一个整数n，表示一共有n对情侣，编号从1到n。同一对情侣编号相同。1<=n<=100
第二行2n个整数a_i，表示编号为a_i的情侣在第i个位置。1<=ai<=n

输出描述:

一个整数，代表最少交换次数。

示例1

输入

3
3 3 2 2 1 1

输出

示例2

输入

4
1 2 3 4 1 2 3 4

输出

算法知识视频讲解

小谷围做题家

package main

import (
    "fmt"
)

func main() {
    var n int
    fmt.Scan(&n)
    arr:=make([]int,2*n)
    for i:=0;i<2*n;i++{
        fmt.Scan(&arr[i])
    }
    ans:=0
    //每次寻找第一位的配对数，并计算相隔的距离，寻找到后把剩下的数组合成新的数组继续寻找
    for len(arr)>0{
        for i:=1;i<len(arr);i++{
            if arr[i]==arr[0]{
                ans+=i-1
                arr=append(arr[1:i],arr[i+1:]...)
                break
            }
        }
    }
    fmt.Print(ans)
}

发表于 2023-03-18 09:26:47 回复(0)