牛牛和妞妞在一天晚上决定一起去看一场情人节演唱会,可是由于这场演唱会实在太出名了,有很多情侣都来观看,牛牛和妞妞不小心被人流冲散了!
维持秩序的人决定,让大家排成一列,相邻两个进去的人(2k-1和2k,k为正整数)坐在相邻座位。但是现在的队伍乱糟糟的,有很多情侣都不在相邻位置。维持秩序的人同意让情侣们跟相邻的人交换位置,直到所有情侣都在2k-1和2k位置上为止。
但是维持秩序的人很没有耐心,所以需要最少的交换次数,你能帮情侣们算出这个次数吗?
第一行一个整数n,表示一共有n对情侣,编号从1到n。同一对情侣编号相同。1<=n<=100
第二行2n个整数ai,表示编号为ai的情侣在第i个位置。1<=ai<=n
一个整数,代表最少交换次数。
3 3 3 2 2 1 1
0
4 1 2 3 4 1 2 3 4
6
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; /** * @Author: coderjjp * @Date: 2020-05-09 17:30 * @Description: * @version: 1.0 */ public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.valueOf(br.readLine()); String[] s = br.readLine().split(" "); ArrayList<Integer> a = new ArrayList<>(); for (int i = 0; i < 2*n; i++) a.add(Integer.valueOf(s[i])); int count = 0; for (int i = 0; i < 2*n - 2; i = i +2){ int next = a.lastIndexOf(a.get(i)); count += (next - i -1); for (int j = next; j >= i + 2; j--) a.set(j, a.get(j - 1)); } System.out.println(count); } }
/* 有个人的思路是这样的: 先把所有人存入集合,从第一个开始找 向后找到与他编号相同的位置,两者相减就是要交换的次数,同时把这个与他编号相同的数剔除, 后面继续上面的操作。 其实如果你仔细思考也是这么回事,比如三个人,编号如下 1 3 1 2 3 2 第一次交换: 1 1 3 2 3 2(交换一次) 第二次交换: 1 1 3 3 2 2(交换一次) 结束。其实你会发现某个数交换完成后,其他的相对位置是不变的,比如,1交换完成后,3之间的相对位置是不变的,2同样 因此我们可以把它放到集合里面,找到与他相同编号的,就把那个剔除(记录交换次数),这也不会印象其他的编号交换 如: 找到第二个1后: 1 3 2 3 2(交换一次) 找到第二个3后: 1 3 2 2(交换一次) 找到第二个2后: 1 3 2(交换0次) */ import java.io.*; import java.util.ArrayList; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader br = new BufferedReader( new InputStreamReader( System.in )); int n = Integer.parseInt(br.readLine()); String[] str = br.readLine().split(" "); ArrayList<Integer> list = new ArrayList<Integer>(); for(int i = 0;i<2*n;i++) list.add(Integer.parseInt(str[i])); //开始计数 int count = 0; int i = 0; while(i<list.size()){ int secIndex = list.lastIndexOf(list.get(i)); count += (secIndex-i-1); list.remove(secIndex); i++; } System.out.println(count); } }借鉴的方法,不喜勿喷
import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < 2 * n; i++) { list.add(scanner.nextInt()); } int result=0; int i=0; while (i<=list.size()-3){ int secondIndex=list.lastIndexOf(list.get(i)); result+=secondIndex-i-1; list.remove(secondIndex); i++; } System.out.println(result); } }