牛牛和妞妞在一天晚上决定一起去看一场情人节演唱会,可是由于这场演唱会实在太出名了,有很多情侣都来观看,牛牛和妞妞不小心被人流冲散了!
维持秩序的人决定,让大家排成一列,相邻两个进去的人(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
#include <bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int a[2*n],mark[2*n]; for(int i=0;i<2*n;i++) { cin>>a[i]; mark[i]=1; } int left=0, right, count=0; while(left<2*n) { if(mark[left]) { mark[left]=0; right=left+1; while(right<2*n && a[right]!=a[left]) { count+=mark[right]; ++right; } mark[right]=0; } left++; } cout<<count<<endl; return 0; }
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); } }
#include <bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n; m = 2*n; int a[m]; bool b[m]; for(int i=0;i<m;i++){ cin>>a[i]; b[i] = true; } int l=0,r=0,cnt=0; for(;l<m;l++){ if(b[l]){ b[l] = false; r = l+1; for(;r<m && a[r]!=a[l];r++) cnt += int(b[r]); b[r] = false; } } cout<<cnt<<endl; return 0; }
k = int(input().strip()) nums = list(map(int, input().strip().split(" "))) times = 0 for i in range(2*k): if i >= len(nums)-1: break for j in range(i+1, 2*k): if j >= len(nums): break if nums[j] == nums[i]: nums.pop(j) times += (j-i-1) break print(times)
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; 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().trim()); String[] strArr = br.readLine().trim().split(" "); ArrayList<Integer> sweethearts = new ArrayList<>(); for(int i = 0; i < 2*n; i++) sweethearts.add(Integer.parseInt(strArr[i])); // 直接暴力解法,从第一个情侣开始安排,计算情侣间的距离,安排好一对情侣就将其从数组中删除 int times = 0; int start = 0; while(start < sweethearts.size()){ int idx = sweethearts.lastIndexOf(sweethearts.get(start)); times += idx - start - 1; sweethearts.remove(idx); start ++; } System.out.println(times); } }
#include <iostream> #include <vector> using namespace std; int main(){ int n; cin >> n; int temp; vector<int> arr; int count = 0; while (cin >> temp) arr.push_back(temp); //1.找到第2i个人 for (int i=0;i<n;++i){ //2.看看他和对象是否坐在一起 if (arr[2*i]==arr[2*i+1]) //2.1 如果坐在一起,去找第2i+2个人 continue; //2.2 如果不坐在一起 else { int j = 2*i+1; //2.2.1 找到他的情侣 for (;j<2*n;++j){ if (arr[j]==arr[2*i]) break; } //2.2.2 把他的情侣换回来 for (int k=j;k>2*i+1;--k){ swap(arr[k],arr[k-1]); ++count; } } //3. 进入下一个循环 } cout << count << endl; return 0; }
#include <bits/stdc++.h> using namespace std; int main(){ int n,ans=0; cin>>n; vector<int> arr(n*2,0); vector<bool> vis(2*n,false); for(int i=0;i<n*2;i++) cin>>arr[i]; for(int i=0;i<arr.size();i++) { if(vis[i]==false) //如果左边未匹配 for(int j=i+1;j<arr.size();j++) if(arr[i]==arr[j]&&vis[j]==false) { //刚好匹配 vis[i]=vis[j]=true; //设置为已匹配 break; } else if(vis[j]==false) //如果不匹配,累加交换次数 ans++; } cout<<ans; return 0; }
#include<bits/stdc++.h> using namespace std; int n, a[100]; int main() { cin >> n; for(int i=0;i<2*n;i++) cin >> a[i]; int ans = 0; unordered_set<int> st; for(int i=0;i<2*n && st.size()<n;i++) { if(st.find(a[i])!=st.end()) continue; for(int j=i+1;a[j]!=a[i];j++) if(st.find(a[j])==st.end()) ans++; st.insert(a[i]); } cout << ans << endl; return 0; }
/*用id标识每个人实际位置,枚举每个人,寻找其情侣的位置,将靠后的情侣换过来 (两者之间人的id都+1,相当于后移一位) */ #include <bits/stdc++.h> using namespace std; const int AX = 1e2 + 66 ; struct Node{ int id ; int v ; }a[AX]; map<int,int>mp ; int main(){ int n ; cin >> n ; int res = 0 ; int len = 2 * n ; for( int i = 1 ; i <= len ; i++ ){ cin >> a[i].v ; a[i].id = i ; } for( int i = 1 ; i < len ; i++ ){ mp[a[i].v] = 1 ; for( int j = i + 1 ; j <= len ; j++ ){ if( a[j].id < a[i].id ) continue ; if( mp[a[j].v] ){ res += ( abs( a[j].id - a[i].id ) - 1 ) ; for( int k = 1 ; k <= len ; k++ ){ //两者之间人位置后移一位 if( a[j].id > a[k].id && a[k].id > a[i].id ) a[k].id ++ ; } a[j].id = a[i].id + 1 ; //修改靠后情侣实际位置 break ; } } mp[a[i].v] = 0 ; } cout << res << endl ; return 0 ; }
#include<iostream> #include<vector> using namespace std; int main(){ int n; cin>>n; vector<int> arr(n*2); for(int i=0;i<n*2;++i) cin>>arr[i]; int cnt=0; for(int i=2*n-1;i>=0;--i)//每次定位到一个情侣 { int j; for(j=0;j<i&&arr[j]!=arr[i];++j);//找到另一个情侣的位置 for(int k=j;k<i-1;++k){//将情侣移动到一起 arr[k]=arr[k+1]; cnt++; } arr[i-1]=arr[i];//放置移动来的情侣 i--;//跳过一个位置,判断下一对情侣 } cout<<cnt<<endl; }
# 思路 # 以数组第一个元素ai[0]为基准,保存其值为first_item # 在ai中找到第二个与first_item相等的数,记录其坐标为 second_item_index # 在数组中删除这两个相等的元素 # 因为每次都会删除首部元素,删除之后迭代前的第二个元素就会成为首个元素 # 而且每次都以第一个元素ai[0]为基准,故 second_item_index 就是两个相同元素的距离 # 结果为 res 累加上 second_item_index n = int(input()) ai = list(map(int, input().split())) res = 0 while len(ai) > 0: first_item = ai[0] del ai[0] # 从list中删除首个元素 second_item_index = ai.index(first_item) # 找到第二个元素的位置(也就是与首个元素的距离) res += second_item_index # 累加距离 del ai[second_item_index] # 从list中删除第二个元素 print(res)
/* 有个人的思路是这样的: 先把所有人存入集合,从第一个开始找 向后找到与他编号相同的位置,两者相减就是要交换的次数,同时把这个与他编号相同的数剔除, 后面继续上面的操作。 其实如果你仔细思考也是这么回事,比如三个人,编号如下 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); } }借鉴的方法,不喜勿喷
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) }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner s = new Scanner(System.in); int n= s.nextInt(); List<Integer> list = new ArrayList<>(2*n); for(int i=0;i<2*n;i++){ list.add(s.nextInt()); } int res=0; while(list.size()>0){ int first = list.get(0); list.remove(0); int lastIndex = list.indexOf(first); res+=lastIndex; list.remove(lastIndex); } System.out.println(res); }偷看了别人的解题思路
// 贪心法,依次在i后面找到当前与a[i]相邻的个数,其中相邻中未被访问过 #include <bits/stdc++.h> using namespace std; const int N = 210; bool st[N]; int a[N]; int n; int main() { cin >> n; n *= 2; for (int i = 1; i <= n; ++ i) { cin >> a[i]; } int ret = 0; for (int i = 1; i <= n; ++ i) { int t = a[i]; if (!st[t]) { st[t] = true; int j = i + 1; while (j <= n && a[j] != t) { if (!st[a[j]]) ret ++ ; j ++ ; } } } cout << ret << endl; return 0; }
#include<iostream> #include<vector> #include<unordered_map> using namespace std; int main() { int n; cin>>n; if(n==0) { cout<<0<<endl; return 0; } vector<int> nums(2*n); for(int i=0; i<2*n; ++i) { cin >> nums[i]; } unordered_map<int, int> maps; int m = 0; for(int i=0; i<2*n; ++i) { if(maps.count(nums[i])==0) { maps[nums[i]] = m; ++m; } nums[i] = maps[nums[i]]; } int count = 0; for(int i=1; i<2*n; ++i) { int num = nums[i]; for(int j=i-1; j>=0; --j) { if(num < nums[j]) { int t = nums[j]; nums[j] = nums[j+1]; nums[j+1] = t; ++count; } } } cout<<count<<endl; return 0; }