佛了呀,被搞死了,为啥不能二分答案。这数据无敌了。谁能解决这个问题呀
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=2501;
int a[maxn];
int m,n;
bool solve(int cishu){
int num1=0;
int num2=0;
int tim=0;
for(int i=0;i<m;i++){
if(a[i]==1)num1++;
else num2++;
if(num1&&num2&&abs(num1-num2)>n){
if(a[i]==1){num1=1;num2=0;}
else {num2=1;num1=0;}
tim++;
}
}
if(num1||num2)tim++;
if(tim<=cishu)return true;
return false;
}
int main()
{ //int x=125+(248-125)>>1;
//cout <<x<<endl;
scanf("%d%d",&m,&n);
for(int i=0;i<m;i++){
scanf("%d",&a[i]);
}
int l=1;
int r=m+1;
for(int i=0;i<1e5;i++){
//cout<<l<<"????????"<<r<<endl;
//int mid=l+((r-l)>>1);
int mid=(l+r)>>1;
//cout<<mid<<endl;
if(solve(mid)){
r=mid;
//cout<<"tesst"<<mid<<endl;
}
else l=mid;
//cout<<"**"<<l<<"??"<<r<<endl;
}
printf("%d\n",l);
return 0;
}