前缀和算法-截断数组

 5057. 截断数组 - AcWing题库

给定一个长度为 n 的正整数数组 a1,a2,…,an 和一个正整数 p。

现在，要将该数组从中间截断，得到两个非空子数组。

我们规定，一个数组的价值等于数组内所有元素之和模 p 的结果。

我们希望，将给定数组截断后，得到的两个非空子数组的价值之和尽可能大。

请你输出这两个非空子数组的价值之和的最大可能值。

输入格式

第一行包含两个整数 n 和 p。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

一个整数，表示价值之和的最大可能值。

数据范围

前 33 个测试点满足 2≤n≤10。
所有测试点满足 2≤n≤105，2≤p≤10000，1≤ai≤106。

输入样例1：

4 10
3 4 7 2

输出样例1：

16

输入样例2：

10 12
16 3 24 13 9 8 7 5 12 12

输出样例2：

13

题意是找到一个点x，然后求 1到x 的区间和加上 x+1到n 的区间和最大，所以只需要遍历 x 的位置，就是1到n，然后根据前缀和算法O(1)得到区间和即可

AC ode：

#include<bits/stdc++.h>
using namespace std;
int arr[100010];
long long s[100010];
long long ans = -1;
int p, n;
int main() {cin >> n >> p;for (int i = 1; i <= n; i++) {cin >> arr[i];s[i] = s[i - 1] + arr[i];}for (int i = 1; i <= n - 1; i++) {long long l = s[i] % p;long long r = (s[n] - s[i]) % p;long long x = l + r;ans = max(ans, x);}cout << ans;
}