P2678 跳石头

题目传送门

这道题主要应用二分查找思想,二分最小的距离,判断方案是否可行

 1 #include<set>
 2 #include<map>
 3 #include<list>
 4 #include<queue>
 5 #include<stack>
 6 #include<string>
 7 #include<cmath>
 8 #include<ctime>
 9 #include<vector>
10 #include<bitset>
11 #include<memory>
12 #include<utility>
13 #include<cstdio>
14 #include<sstream>
15 #include<iostream>
16 #include<cstdlib>
17 #include<cstring>
18 #include<algorithm>
19 using namespace std;
20 
21 int n,m,l=1,r,mid;
22 int a[50005];
23 
24 bool ch(){
25     int tot=0,k=0;
26     for(int i=1;i<=n;i++){
27         if(a[i]-a[k]<mid){
28             tot++;
29         }
30         else{
31             k=i;
32         }
33     }
34     //printf("%d\n",tot);
35     return tot<=m;
36 }
37 
38 int main(){
39     scanf("%d%d%d",&r,&n,&m);
40     for(int i=1;i<=n;i++){
41         scanf("%d",&a[i]);
42     }
43     a[++n]=r;
44     r++;
45     while(l+1<r){
46         mid=(l+r)/2;
47         //printf("%d\n",mid);
48         if(ch()){
49             l=mid;
50         }
51         else{
52             r=mid;
53         }
54     }
55     printf("%d\n",l);
56     return 0;
57 }

 

上一篇:二分答案 & 洛谷 P2678 跳石头


下一篇:洛谷P2678跳石头 二分答案