1

在这里给出的问题中，我必须计算总数。使用插入排序对数组进行排序时所需的交换次数。
这是我的方法

#include <stdio.h>
int main()
{
    int t, N, swaps, temp, i, j;
    scanf("%d", &t);

    while(t--){
        scanf("%d", &N);
        
        int arr[N];
        swaps = 0;
    
        for(i=0; i<N; ++i){

            scanf("%d", &temp);

            j=i;
            while(j>0 && arr[j-1] > temp){
                arr[j] = arr[j-1];
                ++swaps;
                --j;
            }

            arr[j] = temp;
        }
        printf("%d\n", swaps);
    }

    return 0;
}

但是，这个解决方案超出了时间限制。

我怎样才能让它更快？
并且，这个问题的其他更好的解决方案是什么？

4

4 回答 4

9

这是一个名为反转计数的标准问题

这可以使用 O(n*lg(n)) 中的归并排序来解决。这是我计算反转的代码

int a[200001];
long long int count;
void Merge(int p,int q,int r)
{
    int n1,n2,i,j,k,li,ri;
    n1=q-p+1;
    n2=r-q;
    int l[n1+1],rt[n2+1];
    for(i=0;i<n1;i++)
        l[i]=a[p+i];
    for(i=0;i<n2;i++)
        rt[i]=a[q+1+i];
    l[n1]=LONG_MAX;
    rt[n2]=LONG_MAX;
    li=0;ri=0;
    for(i=p;i<=r;i++)
    {
        if(l[li]<=rt[ri])
            a[i]=l[li++];
        else
        {
            a[i]=rt[ri++];
            count+=n1-li;
        }
    }
}
void mergesort(int p,int r)
{
    if(p<r)
    {
        int q=(p+r)/2;

        mergesort(p,q);
        mergesort(q+1,r);
        Merge(p,q,r);
    }
}    
int main()
{
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    count=0;
    mergesort(0,n-1);
    printf("%lld\n",count);
}

基本上反转计数的问题是找到否。对 i 和 j 其中 j>i 使得 a[i]>a[j]

要了解这背后的想法，您应该了解基本的归并排序算法

http://en.wikipedia.org/wiki/Merge_sort

主意：

使用分而治之

除：序列n的大小到两个大小为n / 2的列表征服：递归计算两个列表组合：这是一个技巧部分（在线性时间内完成）

结合使用合并和计数。假设这两个列表是 A，B。它们已经排序。从 A、B 生成输出列表 L，同时还计算反转次数 (a,b)，其中 a 在 A 中，b 在 B 中，并且 a>b。

这个想法类似于合并排序中的“合并”。将两个排序的列表合并为一个输出列表，但我们也计算反转。

每次将 a_i 附加到输出时，都不会遇到新的反转，因为 a_i 小于列表 B 中剩余的所有项。如果将 b_j 附加到输出，则它小于 A 中的所有剩余项，我们增加按 A 中剩余元素数计算的反转计数。

于 2012-08-05T21:08:41.103 回答
2

这让我想起了您可能想查看的类似问题：http ://www.spoj.pl/problems/YODANESS/

在您的问题中，如果需要多次交换，您将没有时间交换所有内容。（想象一下，如果输入的顺序是相反的 9,8,7,6.. 那么您基本上必须将所有内容与所有内容交换。

我认为在你的情况下，每个数字都必须与它左边小于它的所有数字交换。

我建议你使用范围树http://en.wikipedia.org/wiki/Range_tree

范围树的好处是每个节点都可以知道它的左边和右边有多少个节点。您可以非常有效地询问树“有多少数字大于 10”，这就是您对 9 说的有多少交换。

诀窍是在从 i=0 移动到 i=N-1 时构建范围树。在将第 i 个数字插入范围树之前，您可以在每个点查询第 i 个数字的树。

祝你好运！

于 2012-08-04T04:52:48.613 回答
0

我在 C++ 中做了同样的代码，它被接受了，在 spoj 上花费了大约 4.2 秒（http://www.spoj.com/submit/CODESPTB/）。

这是代码片段：

//http://www.spoj.com/problems/CODESPTB/
//mandeep singh @msdeep14
#include<iostream>
using namespace std;
int insertionsort(int arr[], int s)
{
	int current,i,j,count=0;
	for(i=1;i<s;i++)
	{
		current=arr[i];
		for(j=i-1;j>=0;j--)
		{
			if(current<arr[j])
			{
				arr[j+1]=arr[j];
				count++;
			}
			else
				break;
		}
		arr[j+1]=current;
	}
	return count;
}
int main()
{
	int t,n,i,res;
	int arr[100000];
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(i=0;i<n;i++)
		{
			cin>>arr[i];
		}
		res=insertionsort(arr,n);
		cout<<res<<endl;
	}
	return 0;
}

于 2015-06-01T13:46:49.767 回答
0 
#include < stdio.h >
int main() {
   int N, swaps, temp[100], i, j;
   scanf("%d", & N);
   int arr[N];
   swaps = 0;
   for (i = 0; i < N; i++) {
       scanf("%d", & temp[i]);
       j = i;
       while (j > 0 && arr[j - 1] > temp[i]) {
           arr[j] = arr[j - 1];
           ++swaps;
           --j;
       }
       arr[j] = temp[i];
   }
   printf("%d", swaps);
   return 0;
}
于 2015-11-26T13:01:40.787 回答