题目来源：洛谷P2678
跳石头
这是一道标准的 “最大值最小”或“最小值最大“
的题，遇到这种题，我们就可以使用 贪心+二分查找
的方法来做
二分答案/二分查找
有序（单调）的，有界的就可以用二分法查找。
有界：对于本题，我们可以发现，这个所谓的最短跳跃距离显然不能超过一个范围（跳一次从头跳到尾）。也就是说，答案是有一个确定的范围限制的（开头到结尾的距离内），我们就可以考虑一种另外的方法去解决——枚举答案，并去验证答案是否可行，这实际上是一种倒推
二分：那么如何确保我们可以最快的找到答案呢？二分是最好选择
单调：二分的前提条件是什么？是答案区间是整体有序的。我们只考虑合法解，并称之为可行解。考虑所有可行解，我们肯定是要从这些可行解中找到一个最好的作为我们的答案，
这个答案我们称之为最优解。最优解一定可行，但可行解不一定最优。
总结来说，可以使用二分查找的条件：解的上下界确定(l=0,r=L),可以写出判断条件(f(x)<=m),解具有区间单调性(在某个值之前条件都成立，之后都不成立)
本题和 P2855 River Hopscotch
是同一道题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int rocks[50003],ending,num,removed,result;
void finding(int,int);
int main()
{
cin>>ending>>num>>removed;
for(int i=1;i<=num;i++) cin>>rocks[i];
rocks[0]=0; rocks[num+1]=ending;
sort(rocks+1,rocks+num+1);
finding(0,ending);
cout<<result;
return 0;
}
void finding(int m, int n)
{
int mid=(m+n)/2, removing=0;
int now=0,pointer=0;
while(pointer<num){
pointer++;
if(rocks[pointer]-rocks[now]<mid)
removing++;
else
now=pointer;
}
if(m<=n){
if(removing>removed) finding(m,mid-1);
else if(removing<=removed) { result=mid; finding(mid+1,n);}
}
}
|
二分查找模板
非递归形式的二分查找模板
1
2
3
4
5
6
7
8
9
10
11
12
| int l=1,r=ll;
while(l<=r) {
int mid=(l+r)>>1,q=check(mid);
if(check)
{
ll=mid+1;
ans=mid;
}
else
l=mid+1;
}
|
下面是一个二分查找的样例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int stall[100005],cow_num,stall_num,ans;
void finding(int,int);
int main()
{
cin>>stall_num>>cow_num;
for(int i=1;i<=stall_num;i++) cin>>stall[i];
sort(stall+1,stall+stall_num+1);
finding(1,stall[stall_num]);
cout<<ans;
return 0;
}
void finding(int m, int n)
{
int mid=(m+n)/2,now=1,pointer=1,cow_mid=1;
while(pointer<stall_num){
pointer++;
if(stall[pointer]-stall[now]>=mid){
cow_mid++; now=pointer;}
}
if(m<=n){
if(cow_mid>=cow_num) {ans=mid; finding(mid+1,n);}
else finding(m,mid-1);
}
}
|
