c++ - SPOJ上通过TLE的代码优化建议

coder 2024-02-04 原文

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

我有 n 个数字 (1<><=10^5)。我必须在其左侧写下所有小于当前数字的数字的总和，然后对所有 n="" 个数字重复该过程。然后我必须找到所有先前获得的总和的总和。(每个数字=""><><>

例如，

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).

我认为使用二叉索引树(分域树)可以更好地解决此问题的 O(nlogn)。对于每个数字，我将把每个数字添加到一个全局数组 a 中，并执行两个明显的 BIT 操作。我认为这个算法的时间复杂度是 O(nlogn)，如果为真，显然比之前的 O(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/

如果有人能解决，请告诉我。谢谢。

最佳答案

我认为您的方法很好。我对此进行了一点尝试，但没有想出比您所拥有的更好的东西。

虽然您的代码中存在一些错误。有几个地方遭受整数溢出。您应该更改为:

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));

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

关于c++ - SPOJ上通过TLE的代码优化建议，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9826579/

amp 43 int code long c++algorithm optimization data-structures

有关c++ - SPOJ上通过TLE的代码优化建议的更多相关文章

ruby - 如何在 buildr 项目中使用 Ruby 代码？ - 2
如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby
ruby - 通过 rvm 升级 rubygems 的问题 - 2
尝试通过RVM将RubyGems升级到版本1.8.10并出现此错误:$rvmrubygemslatestRemovingoldRubygemsfiles...Installingrubygems-1.8.10forruby-1.9.2-p180...ERROR:Errorrunning'GEM_PATH="/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/ruby-1.9.2-p180@global:/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/rub
ruby-on-rails - Rails 源代码 : initialize hash in a weird way? - 2
在rails源中:https://github.com/rails/rails/blob/master/activesupport/lib/active_support/lazy_load_hooks.rb可以看到以下内容@load_hooks=Hash.new{|h,k|h[k]=[]}在IRB中，它只是初始化一个空哈希。和做有什么区别@load_hooks=Hash.new 最佳答案查看rubydocumentationforHashnew→new_hashclicktotogglesourcenew(obj)→new_has
ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
ruby - 通过 erb 模板输出 ruby 数组 - 2
我正在使用puppet为ruby程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这
ruby - 通过 ruby 进程共享变量 - 2
我正在编写一个gem，我必须在其中fork两个启动两个webrick服务器的进程。我想通过基类的类方法启动这个服务器，因为应该只有这两个服务器在运行，而不是多个。在运行时，我想调用这两个服务器上的一些方法来更改变量。我的问题是，我无法通过基类的类方法访问fork的实例变量。此外，我不能在我的基类中使用线程，因为在幕后我正在使用另一个不是线程安全的库。所以我必须将每个服务器派生到它自己的进程。我用类变量试过了，比如@@server。但是当我试图通过基类访问这个变量时，它是nil。我读到在Ruby中不可能在分支之间共享类变量，对吗？那么，还有其他解决办法吗？我考虑过使用单例，但我不确定这是
ruby - 通过 RVM (OSX Mountain Lion) 安装 Ruby 2.0.0-p247 时遇到问题 - 2
我的最终目标是安装当前版本的RubyonRails。我在OSXMountainLion上运行。到目前为止，这是我的过程:已安装的RVM$\curl-Lhttps://get.rvm.io|bash-sstable检查已知(我假设已批准)安装$rvmlistknown我看到当前的稳定版本可用[ruby-]2.0.0[-p247]输入命令安装$rvminstall2.0.0-p247注意:我也试过这些安装命令$rvminstallruby-2.0.0-p247$rvminstallruby=2.0.0-p247我很快就无处可去了。结果:$rvminstall2.0.0-p247Search
ruby-on-rails - Enumerator.new 如何处理已通过的 block ？ - 2
我在理解Enumerator.new方法的工作原理时遇到了一些困难。假设文档中的示例:fib=Enumerator.newdo|y|a=b=1loopdoy[1,1,2,3,5,8,13,21,34,55]循环中断条件在哪里，它如何知道循环应该迭代多少次(因为它没有任何明确的中断条件并且看起来像无限循环)？最佳答案 Enumerator使用Fibers在内部。您的示例等效于:require'fiber'fiber=Fiber.newdoa=b=1loopdoFiber.yieldaa,b=b,a+bendend10.times.m
ruby-on-rails - 浏览 Ruby 源代码 - 2
我的主要目标是能够完全理解我正在使用的库/gem。我尝试在Github上从头到尾阅读源代码，但这真的很难。我认为更有趣、更温和的踏脚石就是在使用时阅读每个库/gem方法的源代码。例如，我想知道RubyonRails中的redirect_to方法是如何工作的:如何查找redirect_to方法的源代码？我知道在pry中我可以执行类似show-methodmethod的操作，但我如何才能对Rails框架中的方法执行此操作？您对我如何更好地理解Gem及其API有什么建议吗？仅仅阅读源代码似乎真的很难，尤其是对于框架。谢谢! 最佳答案 Ru
ruby - 模块嵌套代码风格偏好 - 2
我的假设是moduleAmoduleBendend和moduleA::Bend是一样的。我能够从thisblog找到解决方案,thisSOthread和andthisSOthread.为什么以及什么时候应该更喜欢紧凑语法A::B而不是另一个，因为它显然有一个缺点？我有一种直觉，它可能与性能有关，因为在更多命名空间中查找常量需要更多计算。但是我无法通过对普通类进行基准测试来验证这一点。最佳答案这两种写作方法经常被混淆。首先要说的是，据我所知，没有可衡量的性能差异。(在下面的书面示例中不断查找)最明显的区别，可能也是最著名的，是你的

c++ - SPOJ上通过TLE的代码优化建议

有关c++ - SPOJ上通过TLE的代码优化建议的更多相关文章

随机推荐