Skip to content

11590: 【原1590】强迫症

题目

题目描述

author: chonps 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1590

Description

BS96发布了一套有m个band柄绘的新badge，kuma先生想要拿到04的badge于是进行了抽抽抽。

kuma先生一共抽了n个badge。他把所有的badge排成一排来统计战果，出于强迫症他希望把所有相同band的badge放在一起。

kuma先生整理badge的方法是交换2个相邻的badge，现在他想知道他最少交换多少次可以达成目的。

Input Format

有多组数据，第一行一个数T表示数据组数，接下来每组数据有2行。

第一行两个数 n, m。

第二行n个数，表示每个badge的band编号。

Output Format

对于每组数据输出一行，形如”Case #X:Y”。X为数据组数，从1开始，Y为最少的交换次数。

Sample Input

3
4 2
1 2 1 2
6 4
2 1 4 3 1 2
8 6
1 3 2 5 5 4 5 2

Sample Output

Case #1: 1
Case #2: 6
Case #3: 5

Limits

  • 40%, n <= 100, m <= 6
  • 70%, n <= 1000, m <= 14
  • 100%, n <= 100000, m <= 18

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！