---
title: "截断数组"
created: 2025-11-28
tags:
  - 算法
---

# 截断数组

## 题目 [截断数组](https://www.acwing.com/problem/content/description/5060/)

![[image-0337bc87.png]]

## 思路分析

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

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

尝试去取一个满足的mid

分析mid怎么得来

![[image-ba59f81b.png]]

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

![[image-8712a56e.png]]

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

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

![[image-237d4250.png]]

所以这个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 更新最大答案即可

## 代码实现

```cpp
#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-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/前缀和与差分相关模型/前缀和/所有奇数长度子数组的和|所有奇数长度子数组的和]]