HDU4004 二分答案

第一道二分答案。。。今天看了大牛的博客，突然发现有个叫“二分枚举答案”的方法好像很牛，于是便搜了些资料。。发现并不是很难，可能是我了解的只是冰山一脚罢了。。。加油ACMer!!!!

#include<stdio.h>

#include<string.h>
#include<algorithm>

using namespace std;

#define max 500000
int d[max],ans;
int L,n,m;

bool OK(int stp){         //判断stp是否为可行解
   int cur=0,curi=0,cnt=0;
   while(cur<L){
       int i,j;
       for(i=curi+1;i<=n;i++){
           if(d[i]<=stp+cur){
               j=i;
           }
           else{
               break;
           }
       }
       if(i==curi+1){
           return false;
       }
       curi=j;
       cur=d[curi];
       cnt++;
   }
   if(cnt>m){
       return false;
   }
   return true;
}

void solve(int s,int e){ //二分求解
   int mid;
   while(s<=e){
       mid=(s+e)>>1;
       if(OK(mid)){
           if(ans>mid){ //如果mid是可行解，则与答案比较
               ans=mid;
           }
           e=mid-1;
       }
       else{
           s=mid+1;
       }
   }
}

int main(){
while(~scanf("%d%d%d",&L,&n,&m)){
   for(int i=1;i<=n;i++){
       scanf("%d",&d[i]);
   }
   d[n+1]=L; //最后一块石头为东岸
   n++;
   sort(d+1,d+n+1);
   ans=L;
   solve(d[1],L);
   printf("%d\n",ans);
}
}

巴特西

HDU4004 二分答案

最新文章

热门文章