截断数组

题目 截断数组

image-0337bc87

思路分析

看到最大可能值 想用二分去写

区间化为左边满足右边不满足的情况

尝试去取一个满足的mid

分析mid怎么得来

image-ba59f81b

划为两非空集合 根据题意得到公式 mid=((s[k]-s[0])%p)+((s[n]-s[k])%p)

image-8712a56e

但是只能知道mid取小了 不知道k到底取大了还是取小了

因为数组不是有序的 我并不知道到底是哪一边的问题 导致这个结果不是ans

image-237d4250

所以这个k是不满足二段性的 不能用二分

但是可以发现 这个公式里面只有k一个变量

那不妨枚举一下k 去求出答案 然后使用max更新出最大的结果即可

k是可以取1的 因为s[1]-s[0]得到的就是第一个元素 即划分成1 n-1的情况

k最大取到n-1 s[n]-s[n-1]得到最后一个元素 即划成n-1 1的情况

在这个范围内枚举k 更新最大答案即可

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long LL;
const int N=1e5+10;
LL s[N];
int n,p;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        s[i]=s[i-1]+x;
    }
    int res=0;
    for(int k=1;k<n;k++){
        int add=((s[k]-s[0])%p)+((s[n]-s[k])%p);
        res=max(res,add);
    }
    cout<<res<<endl;
    return 0;
}

同类题型

视频讲解

⬅️ 局部和 🏠 00-刷题理模型 ➡️ 所有奇数长度子数组的和