首页 > 试题广场 >

排队唱歌

[编程题]排队唱歌

热度指数：6264 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

我们部门要排队唱歌，大家乱哄哄的挤在一起，现在需要按从低到高的顺序拍成一列，但每次只能交换相邻的两位，请问最少要交换多少次

输入描述:

第一行是N（N<50000）,表示有N个人
然后每一行是人的身高Hi（Hi<2000000,不要怀疑，我们以微米计数），持续N行，表示现在排列的队伍

输出描述:

输出一个数，代表交换次数。

示例1

输入

输出

算法知识视频讲解

C/C++

ElonB


	/*
求逆序对数
*/
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n, i, j, ans = 0, temp;
    cin >> n;
    vector<int> a(n);
    for(i = 0; i < n; i++)
        cin >> a[i];
    for(i = 0; i < n; i++)
        for(j = 0; j < i; j++)
            if(a[j] > a[i])
                ans++;
    cout << ans << endl;
    return 0;
}

编辑于 2019-07-11 19:51:25 回复(1)

Java

谁的电脑

即求逆序对，采用归并排序思想，参考https://blog.csdn.net/Fan0628/article/details/88965141

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] height = new int[n];
        for (int i = 0; i < n; i++) {
            height[i] = scanner.nextInt();
        }
//        int count = 0;
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < i; j++) {
//                if (height[j] > height[i]) {
//                    count++;
//                }
//            }
//        }
//        System.out.println(count);
        System.out.println(inversePairs(height));
    }
    private static int inversePairs(int[] arr) {
        int[] copy = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            copy[i] = arr[i];
        }
        int count = inversePairsCore(arr, copy, 0, arr.length - 1);
        return count;
    }
    private static int inversePairsCore(int[] arr, int[] copy, int head, int tail) {
        if (head == tail) {
            return 0;
        }
        // mid的位置
        int mid = (head + tail) >> 1;
        // 递归，分别计算左边和右边内部的逆序对个数
        int leftCount = inversePairsCore(arr, copy, head, mid);
        int rightCount = inversePairsCore(arr, copy, mid + 1, tail);
        // count计数左右两者之间的对数
        int count = 0;
        // i指向mid，j指向tail
        int i = mid;
        int j = tail;
        // 临时数组的指针，指向tail
        int tempCopy = tail;
        while (i >= head && j > mid) {
            // 如果arr[i]大于arr[j]
            if (arr[i] > arr[j]) {
                // i指向的数大于右半部分所有的数，计数加入j-mid
                count += j - mid;
                // 临时数组存放i指向的数，同时tempCopy和i都向前移动
                copy[tempCopy--] = arr[i--];
                // 如果arr[i]小于arr[j]，tempCopy和j都向前移动
            } else {
                copy[tempCopy--] = arr[j--];
            }
        }
        // 移动完之后将没存放的数字存入临时数组，例如[1,2,3,4][5,6,7,8]，
        // 临时数组存完后面四个[5,6,7,8]，j移动到mid移动终止，将剩下的[1,2,3,4]存入临时数组
        for (; i >= head; i--) {
            copy[tempCopy--] = arr[i];
        }
        // 同理，这也是移动完之后将没存放的数字存入临时数组，例如[5,6,7,8][1,2,3,4]，
        // 临时数组存完后面四个[5,6,7,8]，i移动到head移动终止，将剩下的[1,2,3,4]存入临时数组
        for (; j > mid; j--) {
            copy[tempCopy--] = arr[j];
        }
        // 将临时数组复制到原数组，以便递归
        System.arraycopy(copy, head, arr, head, tail - head + 1);
        return (leftCount + rightCount + count);
    }
}

编辑于 2019-07-03 11:25:49 回复(0)

无心2019

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,h[50001],res=0;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>h[i];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(h[j]>h[i])
                res++;
        }
    }
    cout<<res<<endl;
    return 0;
}

发表于 2019-07-02 23:01:57 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, cnt=0;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
            if(a[j]>a[i])
                cnt++;
    cout<<cnt<<endl;
    return 0;
}

发表于 2019-12-14 23:54:06 回复(0)

keashem

用归并排序的思想可以降到 n*logn

import java.util.Scanner;
import static java.lang.System.in;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(in);
        int n = sc.nextInt();
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = sc.nextInt();
        }
        temp = new int[n];
        mergeWay(data, 0, n - 1);
        System.out.println(count);
    }
    public static void mergeWay(int[] data, int begin, int end) {
        if (begin >= end) {
            return;
        }
        int mid = begin + ((end - begin) >> 1);
        mergeWay(data,begin,mid);
        mergeWay(data,mid+1,end);
        merge(data, begin, end, mid);
    }
    public static int[] temp;
    public static int count = 0;
    private static void merge(int[] data, int begin, int end, int mid) {
        int i = begin, j = mid + 1;
        int k = i;
        while (i <= mid && j <= end) {
            count += data[i] <= data[j] ? 0 : mid - i + 1;//这里加的逆序对是这么多，而不是加1
            temp[k++] = data[i] <= data[j] ? data[i++] : data[j++]; //先写上面，这里i，j已变化
        }
        while (i <= mid) {
            temp[k++] = data[i++];
        }
        while (j <= end) {
            temp[k++] = data[j++];
        }
        for (int h = begin; h < k; h++) {
            data[h] = temp[h];
        }
    }
}

发表于 2019-08-03 17:30:47 回复(0)

Python

牛客652172042号

N = int(input())
s = []
c = 0
s = [int(input()) for i in range(N)]
for i in range(N):
    c = c + s.index(min(s))
    s.remove(min(s))
print(c)

1、找最小值，移到首位，去掉这个最小值，
2、循环

发表于 2020-05-03 18:27:00 回复(2)

金际一线天

#include <iostream>
#include <algorithm>
using namespace std;

int heights[50000];

int main(int argc, char* argv[]){
    int N;
    cin >> N;
    for(int idx = 0; idx < N; idx++) cin >> heights[idx];
    int step = 0;
    for(int idx = 1; idx < N; idx++){
        int pos = upper_bound(heights, heights+idx, heights[idx]) - heights;
        if(pos < idx){
            step += idx - pos;
            int tmp = heights[idx];
            for(int i = idx; i > pos; i--) heights[i] = heights[i-1];
            heights[pos] = tmp;
        }
    }
    cout << step << endl;
    return 0;
}

编辑于 2020-04-12 12:33:06 回复(0)

海拉鲁老实人

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int i,j,n,tmp,res=0;
    cin>>n;
    vector<int> people(n);
    for(i=0;i<n;i++)
        cin>>people[i];
    for(i=n-1;i>=0;i--){
        for(j=0;j<i;j++){
            if(people[j] > people[j+1]){
                tmp = people[j];
                people[j] = people[j+1];
                people[j+1] = tmp;
                res++;
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

直接冒泡排序计算交换次数。

通过80%用例，然后就显示超时了，在线模式下查输入输出，显示没有输入输出。

有人能看出问题在哪吗？

编辑于 2020-02-29 17:33:26 回复(4)

WWWWWINGLLING

N = int(input())
H = []
for i in range(N):
    H.append(int(input()))


def func(h):
    '''
    :param h:
    :return:

    每次取第一个数，然后对之后的数进行比较，当比他小时，就插入到前面，否则不动
    完成这个操作后，比它小的数都在左边，大的数都在右边，且该数也在相应的位置上
    然后在对左边和右边进行同样的操作
    '''
    if len(h) == 1&nbs***bsp;len(h) == 0:
        return 0

    temp = h[0]
    j = 0
    count = 0
    for i in range(1, len(h)):
        if h[i] < temp:
            h.insert(j, h.pop(i))
            count += i - j
            j += 1

    count = count + func(h[:j]) + func(h[j + 1:])
    return count


print(func(H))

快排思想

发表于 2020-02-23 10:42:47 回复(0)

C/C++

Shopee内推小虾米

//#include "utils.cpp"
#include <bits/stdc++.h>
using namespace std;
//freopen("temp.in","r",stdin);
#include <bits/stdc++.h>
using namespace std;

/*
    归并排序求逆序对个数
    
	对[l,r]进行归并排序
		1.划分为两半
		2.分别对两部分进行排序
		3.合并结果
*/
vector<int> A,sorted_A;
int merge_sort(int l,int r){
	if(l==r) return 0;
	int ans = 0;
	int mid = l+(r-l)/2;
	//划分、排序
	ans+=merge_sort(l,mid);
	ans+=merge_sort(mid+1,r);
	//合并 
	int i_l = l,i_r = mid+1;
	int end_l = mid,end_r = r;
	int i = l;
	while(i_l<=end_l and i_r<=end_r){
		if(A[i_l]<=A[i_r]){
            //左边的元素小时
			sorted_A[i++]=A[i_l++];
		}
        else{
			sorted_A[i++]=A[i_r++];
			//逆序 当前右边i_r的数与  左边i_l以及它右边所有的数都会逆序
			ans+=(end_l-i_l+1);
		}
	}
    //剩余的
	while(i_l<=end_l) sorted_A[i++]=A[i_l++];
	while(i_r<=end_r) sorted_A[i++]=A[i_r++];
    i=l;
    for(;i<=r;i++)
        A[i]=sorted_A[i];
	return ans;
}
int main(){
//freopen("temp.in","r",stdin);
    int N;
    cin>>N;
    int a;
	A.resize(N);
	sorted_A.resize(N);
    for(int i=0;i<N;i++){
        cin>>a;
		A[i]=a;
		sorted_A[i]=a;
    }
	
    int ans = merge_sort(0,N-1);
	
    cout<<ans<<endl;
    return 0;
}

发表于 2020-02-16 11:12:44 回复(0)

小小呆萌坤

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

//总结目前牛客问题 第一,没有循环输入问题, 第二 有循环输入问题, 第三 输入有多余空格问题 ,第四 中间插入多余空行问题 ....
namespace Test0001
{
    class Program
    {
        public static void Main(string[] args)
        {
            string line;
            while (!string.IsNullOrEmpty(line = Console.ReadLine())) Func(line);
            //Func(Console.ReadLine());
        }
        public static void Func(string line)
        {
            int n = int.Parse(line);
            SortedList<int, int> res = new SortedList<int, int>();
            int count = 0;
            for (int i = 0; i < n; i++)
            {
                int num = int.Parse(Console.ReadLine());
                if (!res.ContainsKey(num)) res.Add(num, 0);
                else res[num]++;
                count += res.Count - res.IndexOfKey(num) + res[num] - 1;
            }
            Console.WriteLine(count);
        }
      
    }
}
者

这题要是用SortList来解决问题比较简单, 思路,由于SortList是有序的,所以无需对他进行任何排序操作,每次只需要找到该数据出现的索引然后用长度减去索引即为他所需要移动的次数,这里需要注意的是,由于可能出现重复数据,所以在有重复数据插入时res[num]++,(相当于出现次数) 计算长度时减去即可

发表于 2019-12-09 11:02:27 回复(0)

Java

JLU小浪

import java.util.Scanner;
/*第一行是N（N<50000）,表示有N个人
 *然后每一行是人的身高Hi（Hi<2000000,不要怀疑，我们以微米计数），持续N行，表示现在排列的队伍
 *输出描述:
 *输出一个数，代表交换次数。*/
//51
public class Main {
    static int[] pi;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] di = new int[n];
		for(int i=0;i<n;i++){
			di[i] = sc.nextInt();
		}
		//复杂度太高，采用归并来计算逆序对个数
		/*int res = 0;
		for(int i=0;i<n-1;i++){
			for(int j=0;j<n-i-1;j++){
				if(di[j]>=di[j+1]){
					int temp = di[j];
					di[j] = di[j+1];
					di[j+1] = temp;
					res++;
				}
			}
		}
		System.out.println(res);*/
		pi = new int[n];
		System.arraycopy(di, 0, pi, 0, n);
		System.out.println(toFind(di, pi, 0, n-1));
		
	}
	static int toFind(int[] arr,int[] copy,int L,int R){
		if(L==R){
			return 0;
		}
		int mid = (R+L)/2;
		int lCount = toFind(arr,copy,L,mid);
		int rCount = toFind(arr, copy, mid+1, R);
		int sum = 0; //已分别有序
		int q = mid; 
		int p = R;
		int temp = R;
		while(q>=L && p>mid){
			if(arr[q]>arr[p]){ //有逆序，计算逆序对
				 sum += p - mid;
				 copy[temp--] = arr[q--];
			}else{
				 copy[temp--] = arr[p--];
			}
		}
		for (; q >= L; q--) {
            copy[temp--] = arr[q];
        }
		for (; p > mid; p--) {
            copy[temp--] = arr[p];
        }
		System.arraycopy(copy, L, arr, L, R-L+1);
		return lCount+rCount+sum;
	}
}

发表于 2019-09-15 11:31:42 回复(0)

Python

贾志统

# insert sort
import bisect
def func(lst, n):
    hh = [lst[0]]
    res = 0
    for i in range(1, n):
        j = bisect.bisect(hh, lst[i])
        bisect.insort(hh, lst[i])
        res += (i-j)
    print(res)


n = int(input())
lst = []
for i in range(n):
    lst.append(int(input()))
func(lst, n)

发表于 2019-08-31 22:51:38 回复(0)

酒馆丶

n = int(input())
list1 = []
for i in range(n):
    list1.append(int(input()))

def InversionNum(lst):
    # 改写归并排序,在归并排序中，每当R部分元素先于L部分元素插入原列表时，逆序对数要加L剩余元素数
    if len(lst) == 1:
        return lst,0
    else:
        n = len(lst) // 2
        lst1,count1 = InversionNum(lst[0:n])
        lst2,count2 = InversionNum(lst[n:len(lst)])
        lst,count = Count(lst1,lst2,0)
        return lst,count1+count2+count

def Count(lst1, lst2,count):
    i = 0
    j = 0
    res = []
    while i < len(lst1) and j < len(lst2):
        if lst1[i] <= lst2[j]:
            res.append(lst1[i])
            i += 1
        else:
            res.append(lst2[j])
            count += len(lst1)-i # 当右半部分的元素先于左半部分元素进入有序列表时，逆序对数量增加左半部分剩余的元素数
            j += 1
    res += lst1[i:]
    res += lst2[j:]
    return res,count

print(InversionNum(list1)[1])

发表于 2019-08-30 21:28:42 回复(0)

C/C++

欧巴禾

#include <vector>
#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int count = 0;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (a[i] > a[j])
                count++;
        }
    }
    cout << count << endl;
}

发表于 2019-08-21 16:57:51 回复(0)

苟在万国

//插入排序
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int num;
    int sum=0;
    while(cin>>num)
    {
        vector<int>vec;
        while(num--)
        {
           int p;
            cin>>p;
            vec.push_back(p);
        }
    for(int i=1;i<vec.size();i++)
    {
        int tmp=vec[i];
        int j;
        for(j=i-1;j>=0;j--)
        {
            if(vec[j]>tmp)
            {
                vec[j+1]=vec[j];
                sum++;
            }
            else break;
        }
        vec[j+1]=tmp;
    }
    }
        
    cout<<sum<<endl;
    return 0;
}

发表于 2019-08-20 23:50:43 回复(0)

XII0001

因为每次只能修改相邻两个值的顺序，即修改一个逆序，故最少操作数为数列的逆序数。由于需要复杂度为O(nlogn)，故考虑归并排序

#include<iostream>

#include<vector>
#include<algorithm>
using namespace std;

int getAns(vector<int> &nums, int s, int e){
if(s>=e) return 0;
int mid = (e-s)/2+s;
int left = getAns(nums, s, mid);
int right = getAns(nums, mid+1, e);
vector<int> tmp(e-s+1);
int ans = 0;
for(int i=mid,j=e; i>=s; i--){
while(j>mid && nums[j]>=nums[i]) j--;
ans += (j-mid);
}
// merge
int k=0;
int i=s,j=mid+1;
while(i<=mid && j<=e){
if(nums[i]<nums[j]) tmp[k++] = nums[i++];
else tmp[k++] = nums[j++];
}
while(i<=mid) tmp[k++] = nums[i++];
while(j<=e) tmp[k++] = nums[j++];
for(int i=s; i<=e; i++) nums[i] = tmp[i-s];
return ans+left+right;
}
int main(){
int n;
while(cin>>n){
vector<int> nums(n);
for(int i=0; i<n; i++) cin>>nums[i];
cout<<getAns(nums, 0, nums.size()-1)<<endl;//是为求解逆序数
}
return 0;
}

发表于 2019-07-04 22:04:14 回复(0)