给定一共n个整数的数组a1,a2,....,an. 你需要求出B数组b1,b2,...,bn. 对于i=1,2...,n-1有式子成立:bi=ai+1+ai (bn=an+a1) 现在有Q个询问,每次给出l,r,根据给定的l和r输出bl+bl+1+....+br.
时间: 2024-03-25 20:40:39 浏览: 144
MAX SUM 给定由n整数(可能为负数)组成的序列 {a1,a2,…,an},求该序列形如ai+ai+1,…,+aj的子段和的最大值。当所有的整数均为负数时定义其最大子段和为0。
5星 · 资源好评率100%
下面是一份C++代码实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, q;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// 计算B数组
vector<int> b(n);
b[0] = a[0] + a[1] + a[n - 1];
for (int i = 1; i < n; i++) {
b[i] = a[i] + a[i - 1];
}
// 处理查询
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
int sum = 0;
for (int i = l; i <= r; i++) {
sum += b[i % n];
}
cout << sum << endl;
}
return 0;
}
```
代码的思路和上面的描述类似,首先读入数组a,然后计算出数组B,最后处理查询并输出结果。需要注意的是,当计算B数组的最后一个元素时,需要使用a1和an,因此在计算时需要特殊处理一下。
阅读全文