这是 2017 年 Google APAC 的一个问题。 Problem D: Sum of Sum
Alice presented her friend Bob with an array of N positive integers, indexed from 1 to N. She challenged Bob with many queries of the form "what is the sum of the numbers between these two indexes?" But Bob was able to solve the problem too easily.Alice took her array and found all N*(N+1)/2 non-empty subarrays of it. She found the sum of each subarray, and then sorted those values (in nondecreasing order) to create a new array, indexed from 1 to N*(N+1)/2. For example, for an initial array [2, 3, 2], Alice would generate the subarrays [2], [3], [2], [2, 3], [3, 2], and [2, 3, 2] (note that [2, 2], for example, is NOT a subarray). Then she'd take the sums -- 2, 3, 2, 5, 5, 7 -- and sort them to get a new array of [2, 2, 3, 5, 5, 7].Alice has given the initial array to Bob, along with Q queries of the form "what is the sum of the numbers from index Li to Ri, inclusive, in the new array?" Now Bob's in trouble! Can you help him out?
对于大型数据集，即使在 C++ 中，直接的解决方案也太低效了。有没有更有效的方法来解决这个问题？
目前我正在通过这个 for 循环来构建最终数组:
multiset<int> sums;
long long int temp = 0;
for (long long int len = 1; len <= n; ++len)
{
for (int start = 0; start+len <= n; ++start)
{
temp = 0;
for (int i = 0; i < len; ++i)
{
temp += arr[start + i]; //arr stores the original array of n digits
}
sums.insert(temp);
}
}
附言:我当前的实现是 O(n^5) 吗？ 我的错误，我现在可以看到它的 O(n^3) 了。谢谢
编辑:到目前为止的答案很有帮助，但对于涉及 n = 200000 项的大型数据集，似乎任何预先计算整个子数组数组的解决方案都太昂贵了。所有提交的解决方案似乎都没有计算子数组的整个数组
最佳答案
如评论中所述，您的解决方案是 O(N^3)，计算为 O(N^2) 乘以 O(N) 总和和多集插入(与 O(N) 相比，您可以忽略) ，请参阅此答案的底部)。
但是交换你的前两个循环，你做的是完全相同的 N*(N+1)/2 求和和插入:
for (int start = 0; start < n; ++start)
{
for (long long int len = 1; start + len <= n; ++len)
{
temp = 0;
for (int i = 0; i < len; ++i)
{
temp += arr[start + i]; //arr stores the original array of n digits
}
sums.insert(temp);
}
}
现在，如果您查看您的 temp 总和，您似乎很明显在做多余的工作。从 start + 1 到 start + 1，然后从 start + 1 到 start + 2，然后从start + 1 到 start + 3 等。对于每个新的 len，您计算的总和是先前值的总和len，加上一项。因此你可以删除这个内部循环:
for (int start = 0; start < n; ++start)
{
temp = 0;
for (long long int len = 1; start + len <= n; ++len)
{
temp += arr[start + len]; //arr stores the original array of n digits
sums.insert(temp);
}
}
所以在 N*(N+1)/2 中你生成了一组值。当然，使用多重集可以隐藏数据排序，但插入通常会花费 log(sums.size())。
单独排序，因为对大小为 S 的集合进行排序需要 S * log(S)，将花费 N*(N+1)/2 * log ( N*(N+1)/2 ) 小于 N*(N+1) * log((N+1)/sqrt(2))。
请注意，因为您有正整数，所以您使用内部循环生成的每组 len 整数都已经排序，因此也许您可以使用它们做一些聪明的事情来加速排序。这也是 multiset 所做的 according to cplusplus.com :
If N elements are inserted, Nlog(size+N) in general, but linear in size+N if the elements are already sorted according to the same ordering criterion used by the container.
关于c++ - 查找子数组的总和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38153101/
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or
我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s
如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:
我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我
这是针对我无法破坏的现有公共(public)API，但我确实希望对其进行扩展。目前，该方法采用字符串或符号或任何其他在作为第一个参数传递给send时有意义的内容我想添加发送字符串、符号等列表的功能。我可以只使用is_a吗？数组，但还有其他发送列表的方法，这不是很像ruby。我将调用列表中的map，所以第一个倾向是使用respond_to?:map。但是字符串也会响应:map，所以这行不通。 最佳答案 如何将它们全部视为数组？String的行为与仅包含String的Array相同:deffoo(obj,arg)[*arg].eac
我已经开始了:defsplit_array(array,size)index=0results=[]ifsize>0whileindex如果我在[1,2,3,4,5,6]上运行它，比如split_array([1,2,3,4,5,6],3)它将产生这个数组:[[1,2,3],[4,5,6]]。在Ruby1.8.7中是否已经有可用的东西可以做到这一点？ 最佳答案 [1,2,3,4,5,6].each_slice(3).to_a#=>[[1,2,3],[4,5,6]]对于1.8.6:require'enumerator'[1,2,3,4
我有一个应用需要发送用户事件邀请。当用户邀请friend(用户)参加事件时，如果尚不存在将用户连接到该事件的新记录，则会创建该记录。我的模型由用户、事件和events_user组成。classEventdefinvite(user_id,*args)user_id.eachdo|u|e=EventsUser.find_or_create_by_event_id_and_user_id(self.id,u)e.save!endendend用法Event.first.invite([1,2,3])我不认为以上是完成我的任务的最有效方法。我设想了一种方法，例如Model.find_or_cr
我想找到给定字符串中的所有匹配项，包括重叠匹配项。我怎样才能实现它？#Example"a-b-c-d".???(/\w-\w/)#=>["a-b","b-c","c-d"]expected#Solutionwithoutoverlappedresults"a-b-c-d".scan(/\w-\w/)#=>["a-b","c-d"],but"b-c"ismissing 最佳答案 在积极的前瞻中使用捕获:"a-b-c-d".scan(/(?=(\w-\w))/).flatten#=>["a-b","b-c","c-d"]参见Rubyde
我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“