摘要：
老板的文章很清楚：https://www.luogu.com.cn/blog/user20197/solution-p26781#include23usingspacestd；4约束N=50010；5intd[N]，N，m；6boolcheck7｛8intcnt=0；//计数器9//此pre的设置需要注意：如果不满足，则不保存，如果满足，则保存当前下标。这样，每次10intpre=0；11for12｛13if14cnt++；15else16pre=i；17｝18if19returnfalse时，都可以保存最后一个跳转的石头；20否则21返回为真；22}23intmain（）24{25intlen，l，r，mid；26cin˃˃len˃˃n˃˃m；27for28{29cin˃˃d[i]；30}31d[0]=0；d[n+1]=长度；//N+1是终点位置32l＝0；r=长度；33while（l＜r）//二进制模板34｛35mid＝/2；36if37l＝mid；38else39r＝mid 1；40｝41cout＜＜l＜＜endl；42返回0；43｝问题含义：有n个隔间，c头牛，以及寻求相邻隔间之间最大距离的想法：两个答案1//前一个问题的代码几乎相同2#include＜iostream＞3#include＜algorithm＞4usingspacestd；5约束N=100010；//参见数据范围6intd[N]，l，r，N，c，mid；如果｛cnt++；pre=i；如果返回true，则检查｛intcnt=0，pre=0；19否则为假；20} 21intmain（）22{23cin˃˃n˃˃c；24for25cin˃˃d[i]；26sort；//记住排序27l=0；r=d[n-1]；28while（l˂r）29{30mid=/2；31if32l=mid；33else34r=mid 1；35}36cout˂˂l˂˂endl；37返回0；38｝当你掌握了板……时，每次只修改检查功能部分。
【跳石头】
题意：需要移掉尽可能少的石头，使得最近的两个石头距离最远。
思路：枚举会超时，二分答案。
大佬的文章写得非常清楚：https://www.luogu.com.cn/blog/user20197/solution-p2678
1 #include <iostream> 2 3 using namespace std; 4 const int N = 50010; 5 int d[N],n,m; 6 bool check(int x) 7 { 8 int cnt = 0;//计数器（用来和m比较） 9 //这个pre的设置需要注意：不满足时就不用保存，满足时保存当前的下标；如此一来才能满足每次保存的是上一次跳的石头 10 int pre = 0; 11 for(int i = 1; i <= n; i ++) 12 { 13 if(d[i] - d[pre] < x) 14 cnt++; 15 else 16 pre = i; 17 } 18 if(cnt > m) 19 return false; 20 else 21 return true; 22 } 23 int main() 24 { 25 int len,l,r,mid; 26 cin>>len>>n>>m; 27 for(int i = 1; i <= n; i++) 28 { 29 cin >> d[i]; 30 } 31 d[0] = 0;d[n+1] = len;//n+1才是终点的位置 32 l=0;r=len; 33 while(l < r)//二分模板 34 { 35 mid=(l+r+1)/2; 36 if(check(mid)) 37 l = mid; 38 else 39 r = mid-1; 40 } 41 cout<<l<<endl; 42 return 0; 43 }
【进击的奶牛】
题意：（须认真看题qaq）有n个隔间，有c头牛，求最大的相邻隔间距离
思路：二分答案
1 //和前一题的代码差不多都一样 2 #include <iostream> 3 #include<algorithm> 4 using namespace std; 5 const int N = 100010;//看清数据范围 6 int d[N],l,r,n,c,mid; 7 bool check(int x) 8 { 9 int cnt = 0,pre = 0; 10 for(int i = 1; i < n ; i++) 11 { 12 if(d[i]-d[pre] >= x) 13 { 14 cnt++; 15 pre = i; 16 } 17 } 18 if(cnt >= c-1)return true; 19 else return false; 20 } 21 int main() 22 { 23 cin >> n >> c; 24 for(int i = 0;i < n; i ++) 25 cin >> d[i]; 26 sort(d,d+n);//记得排序 27 l = 0; r = d[n-1]; 28 while(l < r) 29 { 30 mid = (l+r+1)/2; 31 if(check(mid)) 32 l = mid; 33 else 34 r = mid - 1; 35 } 36 cout << l <<endl; 37 return 0; 38 }
当你掌握了板子……，每次修改的只有check函数的部分。
【P2440木材加工】
![【二分答案】洛谷P2678 [NOIP2015 提高组] 跳石头/P1824 进击的奶牛/P2440木材加工/P1873 砍树第1张](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
![【二分答案】洛谷P2678 [NOIP2015 提高组] 跳石头/P1824 进击的奶牛/P2440木材加工/P1873 砍树第2张](https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)
#include <iostream> #include<algorithm> using namespace std; const int N = 100010; int d[N],l,r,n,k,mid; bool check(int x) { int cnt = 0; for(int i = 0; i < n; i ++) { cnt +=(d[i]/x); } if(cnt >= k) return true; else return false; } int main() { long long ans = 0; cin >> n >> k; for(int i = 0; i < n; i ++) { cin >> d[i]; ans +=d[i]; } l = 0; r = ans/k +1;//最好的情况就是每一段都可以全部利用 while(l < r) { mid = (l+r+1)/2; if(check(mid)) l = mid; else r = mid - 1; } cout << l <<endl; return 0; }
【P1873砍树】
1 #include <iostream> 2 #include<algorithm> 3 4 using namespace std; 5 const int N = 1000010;//看清数据范围 6 int d[N],l,r,n,mid; 7 long long k;//看清数据范围 8 bool check(int x) 9 { 10 long long cnt = 0; 11 for(int i = 0; i < n; i ++) 12 { 13 if(x < d[i]) 14 cnt +=(d[i]-x); 15 } 16 if(cnt >= k) 17 return true; 18 else 19 return false; 20 } 21 int main() 22 { 23 int maxn = 0; 24 cin >> n >> k; 25 for(int i = 0; i < n; i ++) 26 { 27 cin >> d[i]; 28 maxn = max(d[i],maxn); 29 } 30 l = 0; 31 r = maxn; 32 while(l < r) 33 { 34 mid = (l+r+1)/2; 35 if(check(mid)) 36 l = mid; 37 else 38 r = mid - 1; 39 } 40 cout << l <<endl; 41 return 0; 42 }