开发者社区> 问答> 正文

遇到一个Codancer求和问题,求解答

现在Codancer有两个长度均为n的数组a数组和b数组,其中对于a中的 每 个 元 素 a[i] 都 有 (-10^6<=a[i]<=10^6), 对 于 b 中 的 每 个 元 素 b[i] 都 有(0<=b[i]<=n),对于每个 i(1<=i<=n),我们定义区间 [L,R] 是合法的只有 [L,R] 满足下面的条件: 1. 1<=L<=R<=n 2. 0<=i-L,R-i<=b[i] 现在对于每个 i,Codancer 想找到一组合法区间使得 (a[L]+a[L+1]+...a[R]) 最大,并将这个最大值记为 s[i]。现在请计算 (s[1]+s[2]+s[3]+...+s[n])。输入包含一个 n(1<=n<=10^5) 和两个数组 b,a。(b 在前面,a 在后面 )输出 s 数组的和。

展开
收起
游客4skzfvnrxrzbi 2021-12-23 17:01:48 526 0
1 条回答
写回答
取消 提交回答
  • S[1]=a[1]+a[2]=-4,此时 S[1] 最大 S[2]=a[2]+a[3]+a[4]=6, 此时 S[2] 最大 同理可得 S[3]=a[2]+a[3]+a[4]=6, S[4]=a[2]+a[3]+a[4], S[5]=a[2]+a[3]+a[4]+a[5]=2 因此答案为 S[1]+S[2]+S[3]+S[4]+S[5]=16。 image.png

    考虑对 a 数组做前缀和数组 pre, 即 pre[i] 是 (a[1]+a[2]+...+a[i]) 的值,同时对a 做后缀和数组 sa, 即 sa[i] 是 (a[i]+a[i+1]+...a[n]) 的值,那么 s[i] 可以由两部分组成,左边的 a[L]+...+a[i],右边的 a[i]+...+a[R]。左边其实就是找到一个 L,使得 a[L]+...+a[i] 尽可能的大,右边同理 , 因此左边其实就是 max(sa[max(1,i-k)]...sa[i])-sa[i+1]。右边是 max(pre[i]...pre[min(i+k,n)])。对前缀和和后缀和分别建立线段树,O(log(n))求解s[i]即可,答案会爆int,因此需要用 long long 存储。 因此输入:5 [1,2,3,4,4] [-5,1,2,3,-4] 输出:16 注意 : s[1]=-4 s[2]=6 s[3]=6 s[4]=6 s[5]=2 因此最终答案为 16

    2021-12-23 18:51:10
    赞同 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载