rt,WA 了三个点,实在找不出错误 /kk
#include <iostream>
#include <cstdio>
using namespace std;
int n,m,a[2505],sum[2][2505];
inline int mabs(int x)
{
return x<0?-x:x;
}
bool check(int mid)
{
int pos=1,cnt=0;
while(pos<=n)
{
cnt++;
for(int i=n;i>=pos;i--)
{
if(
(mabs((sum[0][i]-sum[0][pos-1])-(sum[1][i]-sum[1][pos-1]))<=m)
||(sum[1][i]-sum[1][pos-1]==0)
||(sum[0][i]-sum[0][pos-1]==0)
)
{
pos=i+1;
break;
}
}
}
return cnt<=mid;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum[0][i]=sum[0][i-1]+(a[i]==1);
sum[1][i]=sum[1][i-1]+(a[i]==2);
}
int l=1,r=n,ans=n;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
printf("%d\n",ans);
return 0;
}