1

配列が与えられa[1..N]ます。配列内の各要素についてa[i]、現在の要素の前に存在する、より小さいすべての要素の合計を書き留めます。配列内のすべての要素の合計を計算する必要があります。

制約:

1<=N<=10^5

すべての要素は 0 から 10^6 の間になります。

ここに私の質問へのリンクがあります: http://www.spoj.com/problems/DCEPC206/。以下に示すアプローチを使用していTIME LIMIT EXCEEDEDますが、SPOJ でエラーが発生します。ソリューションを改善するにはどうすればよいですか?

include 

int main()

{

long n,a[100000],i,j,sum;

printf("enter the number of elements");

  scanf("%ld",&n);

printf("enter the elements of the array");

for(i=0;i<n;i++)

      scanf("%ld",&a[i]);

sum=0;


for(i=1;i<n;i++)

     for(j=i-1;j>=0;j--)

         if(a[i]>a[j])

              sum+=a[j];

printf("\n%ld",sum);

return 0;

}
4

1 に答える 1

0

あなたのものはO（n ^ 2）のオーダーの時間がかかる簡単な実装ですが、ソリューションが受け入れられるには、単純なソートと比較してO（NLogN）時間しかかからないマージソートで行うように、除算と征服を使用する必要がありますバブルソートなどのアルゴリズム

このために、2 ～ 3 行のコードを追加するだけで、Mergesort の実装を少し変更できます。これをよりよく理解するには、配列内の反転をカウントするという問題を解決してください。そのようなすべてのペアの要素。たとえば、配列 1,4,2,5 では、4,2 は反転であると見なされますが、解を得るには 2,5 と 1,2 のようなペアを考慮する必要があります。そのようなすべてのペアで、左の番号を追加し続けます。（それが私たちの仕事をどのように行っているかをよく考えてください!!）

ご参考までに、このマージソートコードを徹底的に調べてください。小さな変更を加えて、正しい受け入れられたソリューションを取得します(合計変数は結果の値を格納します)。

#include <stdio.h>
#include <stdlib.h>
long long int sum;
void merge(long long int c[],long long int arr[],long long int start,long long int middle,long long int end)
{
    long long int i=0,j=start,k=middle;
    while((j<middle)&&(k<end))
    {
        if(arr[j]<arr[k])
        {
            sum=sum+((end-k)*arr[j]);
            c[i]=arr[j];
            i++;j++;
        }
        else
        {
            c[i]=arr[k];
            i++;k++;
        }
    }
    while(j<middle)
    {
        c[i]=arr[j];
        i++;
        j++;
    }
    while(k<end)
    {
        c[i]=arr[k];
        i++;
        k++;
    }

}


void msort(long long int arr[],long long int start,long long int end)
{
    long long int middle=(start+end)/2;
    if((end-start)==1)
    {   return ;
    }
    msort(arr,start,middle);
    msort(arr,middle,end);
    long long int *c;
    c=(long long int*)malloc(sizeof(long long int)*(end-start));
    merge(c,arr,start,middle,end);
    long long int i,j=0;
    for(i=start;i<end;i++)
    {
        arr[i]=c[j];
        j++;
    }
}

void swap (long long int x[],long long int m,long long int n)
{
  long long int t= x[m];
  x[m]=x[n];
  x[n]=t;
}

int main()
{
    int t,i;
    long long int n,*arr,j;
    scanf("%d",&t);
    for(i=0;i<t;i++)
    {
        scanf("%lld",&n);
        arr = ( long long int * ) malloc ( sizeof(long long int) * n + 10);
        for(j=0;j<n;j++)
        {
            scanf("%lld",&arr[j]);

        }

        sum=0;  
        msort(arr,0,n);
//      for(j=0;j<n;j++)
//          printf("%lld ",arr[j]);
        printf("%lld\n",sum);
    }

    return 0;
}
于 2013-06-26T20:14:17.427 に答える