hdu 4004 二分 2011大连赛区网络赛D

时间：2023-12-20 14:31:26

题意：一个长为L的河，中间有n个石子，小青蛙需要跳少于m次过河，判断小青蛙每次跳跃最大距离的最小值

最大值最小，用二分

Sample Input
6 1 2
2
25 3 3
11
2
18
Sample Output
4
11
2015-07-27：备战区域赛专题
 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<map>

 using namespace std;

 #define MOD 1000000007

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 typedef long long ll;

 #define cl(a) memset(a,0,sizeof(a))

 #define ts printf("*****\n");

 const int MAXN=;

 int n,m,tt,L;

 int a[MAXN];

 int check(int m)

 {

     int tot=;

     int k=;    //目前待的石头

     int w=;

     while(tot<L)

     {

         int o=k+;

         if(a[o]-a[k]>m)

         {

             return ;

         }

         while(m>=a[o]-a[k])

         {

             o++;

         }

         k=o-;

         tot+=a[o]-a[k];

         w++;

     }

     return w;

 }

 int main()

 {

     int i,j,k;

     #ifndef ONLINE_JUDGE

     freopen("1.in","r",stdin);

     #endif

     while(~scanf("%d%d%d",&L,&n,&m))

     {

         for(i=;i<=n;i++)    scanf("%d",&a[i]);

         a[]=;

         a[n+]=L;

         sort(a,a+n+);

         a[n+]=;

         int l=,r=L;

         int ans=;

         while(l<=r)

         {

             int mid=(r+l)>>;

             if(check(mid)&&check(mid)<=m)

             {

                 ans=mid;

                 r=mid-;

             }

             else l=mid+;

         }

         printf("%d\n",ans);

     }

 }
 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 using namespace std;

 const int maxn=;

 int n,m,t,L;

 int d[maxn];

 bool fun(int x) //判断青蛙跳x的时候需要跳几次过河，贪心，每次选择能跳最远的

 {

     int now=,tot=;

     int cnt=;

     while(now<L)

     {

         now+=x;

         while(now>=d[tot])   tot++;

         now=d[tot-];

         cnt++;

     }

     if(cnt<=m)  return true;

     else return false;

 }

 int main()

 {

     int i,j,k;

     //freopen("1.in","r",stdin);

     while(scanf("%d%d%d",&L,&n,&m)!=EOF)

     {

         for(i=;i<=n;i++)   scanf("%d",&d[i]);

         sort(d+,d+n+);

         d[]=;

         d[n+]=L;

         d[n+]=;   //用来判断跳几次过河的边界

         int l=,r=L,mid;

         int ans;    //记录最小值

         for(i=;i<=n+;i++) l=l<d[i]-d[i-]?d[i]-d[i-]:l;  //求出两个相邻石子之间的最大距离，也就是青蛙要跳的最小距离

         while(l<=r)

         {

             mid=(l+r)>>;

             if(fun(mid))    ans=mid,r=mid-;

             else l=mid+;

         }

         printf("%d\n",ans);

     }

 }

相关文章