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の2つのリストに征服：再帰的に2つのリストを組み合わせます：これはトリック部分です（線形時間でそれを行うため）

結合は、マージとカウントを使用します。2つのリストがA、Bであるとします。それらはすでにソートされています。反転の数（a、b）もカウントしながら、A、Bから出力リストLを生成します。ここで、aはAにあり、bはBにあり、a>bです。

考え方は、マージソートの「マージ」に似ています。2つの並べ替えられたリストを1つの出力リストにマージしますが、反転もカウントします。

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（http://www.spoj.com/submit/CODESPTB/）では約4.2秒かかります。

コードスニペットは次のとおりです。

//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 に答える