AcWing 5480. 截断数组(前缀和+枚举)
原题链接
中等
作者:
笨小孩一个
,
2024-03-30 17:08:29
,
所有人可见
,
阅读 2
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N =110;
int n,m;
int arr[N];
int f[N];
vector<int> res;
int main()
{
//怎么快速判断一个区间是不是平衡数组: 用前缀和,奇数为-1 ,正数为1
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>arr[i];
for(int i=1;i<=n;i++)
{
if(arr[i]%2==0)f[i]=1;
else f[i]=-1;
}
for(int i=1;i<=n;i++) f[i]+=f[i-1];
for(int i=2;i<=n-2;i++)
{
if(f[i]==0&&f[n]-f[i]==0) res.push_back(abs(arr[i]-arr[i+1]));
}
sort(res.begin(),res.end());
int cnt =0;
if(!res.size())cout<<0<<endl;
else {
for (auto k:res)
{
if(k<=m){
cnt++;
m-=k;
}
}
cout<<cnt<<endl;
}
return 0;
}