题一
确认答案区间，二分枚举，check（mid）在答案的左边还是右边，然后改l,r
A
思路是距离小于mid的石子舍掉，大于mid的石子作为起点
#include <iostream> #include <algorithm> const int N = 1e5 + 10; int a[N]; int l,n,m,res; using namespace std; bool check(int mid){ //now和cnt未初始化是此题卡题原因（定义成全局变量了，初始化的意识不够强》 int now = 0; int cnt = 0; for(int i = 1;i <= n + 1;i++){ if(a[i] - a[now] < mid){ cnt ++; } else now = i; } if(cnt <= m) return true; else return false; } int main(){ cin >> l >> n >> m; for(int i = 1;i <= n;i++){ cin >> a[i]; } a[0] = 0; a[n+1] = l; sort(a,a+n+1); int L = 1,R = l; while(L < R){ int mid = (L + R + 1) / 2; if(check(mid)) L = mid,res = mid; else R = mid - 1; // cout << "l=" << L << "r=" << R << endl; // 除了浮点数二分外，l与r的操作方式还是按照yxc的模板 // 照着题解写都写了40分钟，此题必须重做 } cout << res << endl; return 0; }
// 除了浮点数二分外，l与r的操作方式还是按照yxc的模板 ，yxc模板是永远的神，用就完了，不要质疑边界处理，只有l,r取值要注意
// 照着题解写都写了40分钟，此题必须重做
now和cnt未初始化是此题卡题原因（定义成全局变量了，初始化的意识不够强
B
思路是累加值超过了mid，组数加一
//b题 ac代码 #include<iostream> #include<cstdio> #include<algorithm> using namespace std; #define int long long const int N = 1e6;int minn = 1e12;int n,m;int a[N],res; bool check(int mid){ //cnt不知为何在debug过程中写成了0，导致；一直不过 int cnt = 1,sum = 0; for(int i = 0;i < n;i++){ if(sum + a[i] <= mid){ sum += a[i]; } else { sum = a[i]; cnt ++; } } // cout << "sum =" << sum << " " << "cnt=" << cnt << endl; if(cnt <= m) return true; else return false; } signed main(){ //debug一小时，发现是l，r设置有问题>? cin >> n >> m; int r=0,l = 0; for(int i = 0;i < n;i++){ cin >> a[i]; r += a[i]; l = max(a[i],l); } while(l < r){ int mid = (l + r) >> 1; if(check(mid)) r = mid,res = mid; else l = mid + 1; } cout << res << endl; return 0; }
//cnt不知为何在debug过程中写成了0，导致；一直不过
//debug一小时，发现是l，r设置有问题>?应该要尽量贴合答案区间
//题目数据水了，我没有多组输入也ac了
总结
做得好：做的不好
做得不好：
1、没有提前查看二分答案题的套路，死磕题目浪费了大把时间。
2、怀疑yxc的模板正确性
反思：
1、下次做二分题单前，先把二分博客看完，看多几道例题答案，了解知识点套路与运用再去做题。
2、二分debug时不用考虑二分边界处理出错，注意l，r取值与check函数内变量的初始化。
