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 实现。为了更好地理解这一点，请通过计算数组中的反转问题。（http://www.geeksforgeeks.org/counting-inversions/）然后你会意识到你只需要考虑本质上与反转相反的对并添加所有较小的对所有此类对的元素。例如 - 在数组 1,4,2,5 中考虑 4,2 是反转，但我们必须考虑像 2,5 和 1,2 这样的对来获得解决方案。在每一对这样的对中，继续添加左边的号码。（仔细想想它是如何完成我们的工作的！！）

供您参考，请彻底阅读此合并排序代码，其中我有一些小的更改以获得正确的可接受的解决方案。（sum 变量存储结果值）

#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 回答