首页 > 代码库 > 测试5T2-手套

测试5T2-手套

问题描述
你现在有N对手套,但是你不小心把它们弄乱了,需要把它们整理一下。N对手套被一字排开,每只手套都有一个颜色,被记为0~N-1,你打算通过交换把每对手套都排在一起。由于手套比较多,你每次只能交换相邻两个手套。请你计算最少要交换几次才能把手套排整齐。
输入格式
输入第一行一个N,表示手套对数。
第二行有2N个整数,描述了手套的颜色。每个数都在0~N-1之间,且每个数字都会出现恰好两次。
输出格式
一行,包含一个数,表示最少交换次数。
样例输入
2
0 1 0 1
样例输出
1
数据范围
30%的数据N≤9;
60%的数据N≤1000;
100%的数据N≤200,000。

这道题题目看错,吐血~~我以为是求多少次把手套从大到小排好序~~

这题就是先考虑一下贪心做法——每次找到一对手套的前半只,把后半只换到它后面,不会对原序列其他数产生影响

然后考虑一下操作,如果两个手套位置分别为a,b的话,这样我们只要知道a和b之间所有还没换到a之前的手套数量就可以了

 

测试5T2-手套