建议优化代码以在SPOJ上传递TLE

Question

我正在尝试解决这样的问题:

我给了n个数字(1 <= n <= 10 ^ 5).我必须在左边写下所有数字的总和,这些数字小于当前数字并重复所有n个数字的过程.然后我必须找到所有先前获得的和的总和.(每个数字N,0 <= N <= 10 ^ 6).

例如,

1 5 3 6 4
less1 less5 less3 less6 less4
 (0) + (1) + (1)+(1+5+3)+(1+3)
  0  +  1  +  1  +  9  +  4
= 15

这个问题的一个简单的解决方案是运行两个循环,并且对于给定数字中的每一个,找到小于该数字的所有数字的总和,最后给出这些和的总和作为输出.时间复杂度为O(n ^ 2) .

我认为使用二进制索引树(Fenwick树)可以更好地解决这个问题的O(nlogn)解决方案.对于每个数字,我将在全局数组a中添加每个数字并执行BIT的两个明显操作.我认为该算法的时间复杂度为O(nlogn),如果为真,则明显优于之前的O(n ^ n ^ 2).

我用C++实现了代码.

#include<iostream>
#include<cstdio>

using namespace std;

#define max 1000001

long int a[max];

void add(long int v,int idx){
while(idx<max){
    a[idx] += v;
    idx += (idx & -idx);
}
}

long int sum(int idx){
long int s=0;
while(idx>0){
    s += a[idx];
    idx -= (idx & -idx);
}
return s;
 }

 int main()
 {
int t;
scanf("%d",&t);
for(int w=0;w<t;w++){
    int n;
    scanf("%d",&n);

    for(int i=0;i<max;i++)
        a[i]=0;

    int arr[n];
    for(int i=0;i<n;i++)
        scanf("%d",&arr[i]);

    long long res=0;

    for(int i=0;i<n;i++){
        if(arr[i]!=0){
           add(arr[i],arr[i]);
           res += (sum(arr[i]-1));
                     }  
    }

    printf("%lld\n",res);
}

return 0;
}

我有两个问题:

首先,我做得对吗？/我的逻辑是否正确？

第二,如果我把时间复杂度定为O(nlogn)那么为什么它运行缓慢？你能帮助我进一步优化吗？

已经接受了1.41秒.同时我更新了我最终接受的代码.有关优化的建议吗？

基于这些评论,我尝试了自己的功能,以实现更快的I/O,但仍然没有按照我的方式进行.这是我的快速I/O功能:

 inline int read(){
char c=getchar_unlocked();
int n=0;
while(!(c>='0' && c<='9'))
    c=getchar_unlocked();

while(c>='0' && c<='9'){
    n=n*10 + (c-'0');
    c=getchar_unlocked();   
}
return n;
 }

这是问题的链接:

http://www.spoj.pl/problems/DCEPC206/

如果有人能够解决它,请告诉我.谢谢.

Answer 1

我认为你的方法是一个很好的方法。我已经对此进行了一点尝试，但没有想出任何比你所拥有的更好的东西。

不过，您的代码中存在一些错误。有几个地方存在整数溢出问题。您应该更改为：

long long a[max];

和

long long sum(int idx){
long long s=0;

更明显的错误是您正在对小于或等于当前数字的数字求和。要解决此问题，您可以添加第二个全局数组来跟踪每个值的计数：

int b[max];
...
...
    for(int i=0;i<max;i++)
        a[i]=b[i]=0;
    ...
    ...
        res += (sum(idx)-(++b[idx]*val));

可能有一种更有效的方法来修复该错误，但总的来说，它似乎仍然是一个快速的解决方案。