首页 > 试题广场 > 美妙的约会
[编程题]美妙的约会
  • 热度指数:5709 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
牛牛和妞妞在一天晚上决定一起去看一场情人节演唱会,可是由于这场演唱会实在太出名了,有很多情侣都来观看,牛牛和妞妞不小心被人流冲散了!
维持秩序的人决定,让大家排成一列,相邻两个进去的人(2k-1和2k,k为正整数)坐在相邻座位。但是现在的队伍乱糟糟的,有很多情侣都不在相邻位置。维持秩序的人同意让情侣们跟相邻的人交换位置,直到所有情侣都在2k-1和2k位置上为止。
但是维持秩序的人很没有耐心,所以需要最少的交换次数,你能帮情侣们算出这个次数吗?

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


输出描述:
一个整数,代表最少交换次数。
示例1

输入

3
3 3 2 2 1 1

输出

0
示例2

输入

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;
}

发表于 2019-07-12 20:52:04 回复(2)
# 思路
# 以数组第一个元素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)

编辑于 2019-09-24 14:59:30 回复(3)
/*
有个人的思路是这样的:
先把所有人存入集合,从第一个开始找
向后找到与他编号相同的位置,两者相减就是要交换的次数,同时把这个与他编号相同的数剔除,
后面继续上面的操作。

其实如果你仔细思考也是这么回事,比如三个人,编号如下
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);
    }
}
借鉴的方法,不喜勿喷
发表于 2020-05-04 14:03:13 回复(0)
Java解法,算法简单,但复杂度为O(n2)

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);
    }
}



编辑于 2020-03-01 15:51:40 回复(1)
#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;
}

发表于 2019-08-29 01:20:35 回复(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)

发表于 2019-08-28 14:12:44 回复(0)
每次考虑排头的伴侣。
如1 2 3 4 1 2 3 4,先考虑让1这一对情侣相邻,如果把第一个1换到后面去,对于情侣2 3 4来说,由于中间增加了一个人,之后要配对2 3 4情侣会交换更多次数,所以把后面那个1换到第一个2的位置,需要进行3次换位,变为1 1 2 3 4 2 3 4。由于将第二个1换到前面去了,使得它原本位置的两个邻居的距离减少了1,我们忽略1这一对情侣,使序列变为2 3 4 2 3 4,然后用相同的方法再去安排2这一对情侣,直到所有情侣都配对成功即可。
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);
    }
}



发表于 2021-01-31 10:15:44 回复(0)
#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;
}


发表于 2020-07-04 22:52:12 回复(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;
}


发表于 2020-07-02 22:20:02 回复(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;
}

编辑于 2020-06-10 23:57:40 回复(0)
a,b,k = int(input()),input().split(),0
for i in range(0,a * 2,2):
    for j in range(i + 1,a * 2):
        if b[j] == b[i]:
            b = b[:i + 1] + [b[j]] + b[i + 1:j] + b[j + 1:]
            k += len(b[i + 1:j])
            break
print(k)

发表于 2020-03-18 22:12:06 回复(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 ; 
}


编辑于 2020-02-11 12:24:06 回复(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;
}

发表于 2019-07-26 21:45:46 回复(0)
#include<iostream>
#include<algorithm>
#include <vector>
#include<string>
#include <iomanip> //保留小数
#include<limits.h>  //使用int_max
#include <map>
#include<unordered_map>
#include<set>
usingnamespacestd;
 
intmain() {
    intn;
    while(cin >> n)
    {
        vector<int> vec;
        intt = n * 2;
        while(t--) {
            inttmp;
            cin >> tmp;
            vec.push_back(tmp);
        }
        intres = 0;
        while(!vec.empty())
        {
            auto i = vec.begin();
            intcnt = 0;
            for(auto it = vec.begin() + 1; it != vec.end(); it++) {
                cnt++;
                if(*it == *i) {
                    vec.erase(it);
                    vec.erase(i);
                    res += cnt - 1;
                    break;
                }
            }
        }
        cout << res;
    }
    return0;
}
发表于 2019-07-02 11:39:47 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;
    int number;
    vector<int> a;
    for (int i = 0; i < 2*n; i++)
    {
        cin >> number;
        a.push_back(number);
    }
    int sum = 0;
    int g = 0;
    for (int i = 1; i < 2 * n; i=i+2)
    {
        auto it=find(a.begin()+i,a.end(),a[i-1]);
        for (vector<int>::iterator j=it; j>a.begin()+i; j--)
        {
            int temp = 0;
            temp = *j;
            *j = *(j-1);
            *(j - 1) = temp;
            sum++;
        }
    }
    cout << sum << endl;
    return 0;
}
发表于 2021-02-04 16:24:29 回复(0)
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);
       
    }  
偷看了别人的解题思路
发表于 2020-08-13 16:18:08 回复(0)
利用c++ vector存储所有的元素,从第一个元素起查找后面的配对元素的index,找到之后,则交换次数为index-i-1,然后累加到count中,最后输出,因为vector不存在查找元素的函数,所以自己写了一个

#include"iostream"
#include"vector"

using namespace std;

int findElement(std::vector<int> vec,int element)
{
    for(int i=vec.size()-1;i>=0;i--)
    {
        if(vec[i]==element)
        {
            return i;
        }
    }
    return -1;
}

int main()
{
    
    int n,m;
    std::cin >> n;

    std::vector<int> vec;
    
    for (int i=0;i<2*n;i++)
    {
        std::cin >> m;
        vec.push_back(m);
    }

    int count = 0;
    for (int i = 0; i < vec.size(); i++)
    {
        int secIndex = findElement(vec, vec[i]);
        if (secIndex != -1)
        {
            count += secIndex - i - 1;
            std::vector<int>::iterator it = vec.begin() + secIndex;
            vec.erase(it);
        }
    }
    std::cout << count << std::endl;
}
编辑于 2020-08-07 19:06:10 回复(0)
// 贪心法,依次在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;
}

发表于 2020-07-21 20:34:05 回复(0)
和求逆序对的个数类似的,只不过这种方法需要对id进行重新标记,逆序对的个数和插入排序的个数相同,还可以用归并算法进行优化。
#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;
}


编辑于 2020-07-19 16:27:37 回复(0)
  • 暴力法,挨个找相同的值,之后模拟交换过程把这两个值弹出,重复计算剩下的情侣们。
N = int(input())
nums = list(map(int,input().split()))

times = 0
while len(nums) > 1:
    temp = nums.pop()
    if temp == nums[-1]:
        nums.pop()
        continue
    for i in range(len(nums)-1,-1,-1):
        if temp == nums[i]:
            times += (len(nums)-i-1)
            nums.pop(i)
            break
print(times)
发表于 2020-07-16 12:36:27 回复(0)