BZOJ 1650 [Usaco2006 Dec]River Hopscotch 跳石子：二分

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1650

题意：

　　数轴上有n个石子，第i个石头的坐标为Di，现在要从0跳到L，每次条都从一个石子跳到相邻的下一个石子。

　　现在FJ允许你移走M个石子，问移走这M个石子后，相邻两个石子距离的最小值的最大值是多少。

题解：

　　二分。

　　check函数：

　　　　（1）求出每个区间的长度len[i] = dis[i+1] - dis[i]。

　　　　（2）对于第1到n-1个区间，如果len[i] > now，则去掉右端点的石头，cnt++。

　　　　　　即：len[i+1]+=len[i]; len[i]=len[i+1];

　　　　（3）对于第n个区间，如果len[n] > now，则只能去掉左端点的石头，cnt++。

　　　　一旦cnt > m，就return false。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 #define MAX_N 50005

 using namespace std;

 int n,m,l;

 int ans;

 int dis[MAX_N];

 int len[MAX_N];

 void read()

 {

     cin>>l>>n>>m;

     dis[]=;

     dis[n+]=l;

     for(int i=;i<=n;i++)

     {

         cin>>dis[i];

     }

 }

 bool check(int now)

 {

     for(int i=;i<=n;i++)

     {

         len[i]=dis[i+]-dis[i];

     }

     int cnt=;

     for(int i=;i<n;i++)

     {

         if(len[i]<now)

         {

             len[i+]+=len[i];

             len[i]=len[i+];

             cnt++;

             if(cnt>m) return false;

         }

     }

     if(len[n]<now && cnt+>m) return false;

     return true;

 }

 void solve()

 {

     sort(dis+,dis+n+);

     int lef=;

     int rig=l;

     while(rig-lef>)

     {

         int mid=(lef+rig)/;

         if(check(mid)) lef=mid;

         else rig=mid;

     }

     if(check(rig)) ans=rig;

     else ans=lef;

 }

 void print()

 {

     cout<<ans<<endl;

 }

 int main()

 {

     read();

     solve();

     print();

 }

巴特西

BZOJ 1650 [Usaco2006 Dec]River Hopscotch 跳石子：二分

最新文章

热门文章