简单二分答案

青蛙游戏

Description

青蛙王国运动会开始了，最受欢迎的游戏是铁蛙三项赛，其中一项是跳跃过河项目。这个项目需要青蛙运动员通过跳跃过河。河的宽度是L。在河面上有直线排列的n个石头。青蛙可以利用这些石头跳跃过河，如果落入河中则失败。青蛙们能够跳跃的最多次数是m。现在铁蛙门想要知道他们至少需要具备多大的跳跃距离，才能够顺利完成比赛。

Input

输入包含了多个测试样例，测试样例第一行包含了3个正整数L，n，m。接下来的i(i<=n)行中，第i表示第i个石头距离起跳岸边的距离，其中不存在两个石头距离相同的情况。

Output

输出一个整数，表示铁蛙要完成比赛需要具备的最低跳跃能力。

Sample Input

Sample Output

4
11

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 //const double PI=acos(-1);
17 #define Bug cout<<"---------------------"<<endl
18 const int maxn=1e5+10;
19 using namespace std;
20 
21 int A[maxn];//存放每块石头到开始处的距离
22 int B[maxn];//存放石头之间的差值 
23 
24 int main()
25 {
26     int L,n,m;
27     while(~scanf("%d %d %d",&L,&n,&m))
28     {
29         memset(A,0,sizeof(A));
30         memset(B,0,sizeof(B));
31         int MAX=0;//答案不可能会小于石头差值中的最大值，否则这两块石头一定跳不过去
32         for(int i=1;i<=n;i++)
33         {
34             scanf("%d",&A[i]);
35             if(i==n)
36                 A[i+1]=L;//最后要跳到河岸上 
37         }
38         sort(A+1,A+1+n+1);
39         for(int i=1;i<=n+1;i++)
40         {
41             B[i]=A[i]-A[i-1];
42             if(B[i]>MAX)
43                 MAX=B[i];
44         }
45         int l=MAX;
46         int r=L;
47         int mid;
48         while(l<=r)//二分查找答案 
49         {
50             mid=(l+r)>>1;//二分法的中值（即初始青蛙能跳的最大距离）
51             int step=0;//记录跳的步数 
52             int sum=0;//检验到这个石头需要跳的距离
53             for(int i=1;i<=n+1;i++)//此处用到贪心，一次尽量多跳几个石头
54             {
55                 if(sum+B[i]<=mid)//可以继续跳 
56                     sum+=B[i];
57                 else//不可以继续跳
58                 {
59                     step++;//跳的次数加1
60                     sum=B[i];//下一次从这个石头起跳
61                 }
62                 if(i==n+1&&sum!=0)//跳到岸了，处理一下
63                     step++;
64             }
65             if(step>m)
66                 l=mid+1;
67             else
68                 r=mid-1;
69         }
70         printf("%d
",mid);
71     }
72     return 0;
73 }

CodeForces 991C Candies

http://codeforces.com/problemset/problem/991/C

题意：

给出一个数n，表示有n块蛋糕，有两个人a，b。a每次可以取k块蛋糕（如果剩下的蛋糕不足k，则一次性取完），

b每次取当前蛋糕的十分之一（如果不是整数的话，向下取整，例如，有9块蛋糕的话，那么b取0块）

求一个最小的k，使得a所取的蛋糕至少大于n的一半。

思路：

二分枚举k然后判断是否满足条件即可。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 #define Bug cout<<"---------------------"<<endl
16 const int mod=1e9+7;
17 const int maxn=2e5+10;
18 using namespace std;
19 
20 int judge(LL n,LL k)
21 {
22     LL t=n;
23     LL sum1=0;
24     LL sum2=0;
25     while(t)
26     {
27         if(t>=k)
28         {
29             t-=k;
30             sum1+=k;
31         }
32         else
33         {
34             sum1+=t;
35             t=0;
36         }
37         sum2+=t/10;
38         t-=t/10;
39     }
40     if(sum1>=sum2)
41         return 1;
42     else
43         return 0;
44 }
45 
46 int main()
47 {
48     LL n;
49     scanf("%lld",&n);
50     LL l=1;
51     LL r=n;
52     LL mid;
53     LL ans;
54     while(l<=r)
55     {
56         mid=(l+r)>>1;
57         if(judge(n,mid))
58         {
59             ans=mid;
60             r=mid-1;
61         }    
62         else
63             l=mid+1;
64     }
65     printf("%lld
",ans);
66     return 0;
67 }