做的不错的网站,商丘网络有限公司,克州建设工程信息网,视频软件观看免费高清下载5057. 截断数组 - AcWing题库 给定一个长度为 n 的正整数数组 a1,a2,…,an 和一个正整数 p。 现在#xff0c;要将该数组从中间截断#xff0c;得到两个非空子数组。 我们规定#xff0c;一个数组的价值等于数组内所有元素之和模 p 的结果。 我们希望#xff0c;将给定数组… 5057. 截断数组 - AcWing题库 给定一个长度为 n 的正整数数组 a1,a2,…,an 和一个正整数 p。 现在要将该数组从中间截断得到两个非空子数组。 我们规定一个数组的价值等于数组内所有元素之和模 p 的结果。 我们希望将给定数组截断后得到的两个非空子数组的价值之和尽可能大。 请你输出这两个非空子数组的价值之和的最大可能值。 输入格式 第一行包含两个整数 n 和 p。 第二行包含 n 个整数 a1,a2,…,an。 输出格式 一个整数表示价值之和的最大可能值。 数据范围 前 33 个测试点满足 2≤n≤10。 所有测试点满足 2≤n≤1052≤p≤100001≤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 的区间和加上 x1到n 的区间和最大所以只需要遍历 x 的位置就是1到n然后根据前缀和算法O(1)得到区间和即可
AC ode
#includebits/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;
}
