二分答案求助。
  • 板块P1564 膜拜
  • 楼主abcd156555
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/11/17 15:08
  • 上次更新2023/11/5 07:51:11
查看原帖
二分答案求助。
47496
abcd156555楼主2020/11/17 15:08

佛了呀,被搞死了,为啥不能二分答案。这数据无敌了。谁能解决这个问题呀

#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;
}
2020/11/17 15:08
加载中...