🌰1、方程求根
晴问算法
1️⃣即求f(x) = x^3 + x^2 + x - a = 0的根，又因为要求精确到0.01，所以eps至少设置为1e-3或者更小；
2️⃣求导得3x^2 + 2x + 1 = 2x^2 + x^2 + 2x + 1 = 2x^2 + (x+1)^2 > 0， 所以f(x)是单调递增函数；
3️⃣估计查找区间初值：因为a的取值区间是-100-100，所以我们让查找区间的初值为【-100 ， 100】
这样一定能包含所有可能的解。
对于闭区间【left, right]:
若f(mid) > 0,说明mid比解大，则让right = mid;
若 < 0, 说明mid比解小，则让left = mid;
当right - left <= eps 则可跳出循环。返回left or mid， 即进入循环条件是right-left > eps，最终取两位小数输出
#include <iostream>
using namespace std;
const double EPS = 1e-3;//
int a;
double f(double x){return x*x*x + x*x + x -a ;
}
double binarySearch() {double left = -100, right = 100, mid;while (right - left > EPS) {mid = (left + right) / 2;if (f(mid) > 0) {right = mid;} else {left = mid;}}return left;//or mid,但是运行时间会更长。
}int main() {cin >> a;printf("%.2f", binarySearch());return 0;
}🌰2、装水问题
晴问算法
1️⃣我们要求h,所以应当对h进行二分查找，又要求精确到2位小数，所以eps至少是1e-3;
2️⃣又显然随着h的增大，s1的面积也增大，所以当我们对h进行二分查找时，
若s1/s2 > r说明s1过大了，应该缩小右边界，即让right = mid;
若s1/s2 < r说明s1过小了，应该扩大左边界，即让left = mid;
当right - left <= eps，就找到了满足要求的解，跳出循环。返回左边界。输出带前2位小数的格式。
3️⃣二分查找区间的初值应该是[0, R], 因为它覆盖了h所有可能的取值。
为了统一代码，我们定义函数f(R, h) = s1/s2
#include <cstdio>
#include <cmath>
const double EPS = 1e-3;
const double PI = acos(-1.0);
double f(double R, double h) {double alpha = 2 * acos((R - h) / R);double L = 2 * sqrt(R * R - (R - h) * (R - h));double S1 = alpha * R * R / 2 - L * (R - h) / 2;double S2 = PI * R * R / 2;return S1 / S2;
}
double binarySearch(double R, double r){double left = 0, right = R, mid;while(right - left > EPS){mid = (left + right) / 2;if(f(R, mid) > r)right = mid;elseleft = mid;}return left;
}
int main(){int R;double r;scanf("%d%lf", &R, &r);printf("%.2lf\n", binarySearch(R, r));
}🌰3、木棒切割问题
晴问算法
1️⃣题目要求切割后每根木棒的最大长度，那么就应该对切割后每根木棒的长度进行二分查找，那么查找区间初值为[0,max(木棒长度)]
2️⃣又显然，要求切割后得到的木棒段数越多即k越大，长度就会越小，设函数Num(l)为长度为l时可得到的最多段数
对于二分查找区间[left, right]:
若Num(mid) < k, 不满足至少k段的条件，说明mid不可能是解，且应该让k大一些，那就应该让mid小一点，即让right = mid -1;
若Num(mid) >= k,满足至少k段的条件，说明mid有可能是解，但还需让mid大一点继续往右检查看是否还有更长的mid满足至少k段，那就让left = mid;
当left == right说明找到了最大长度即解，因此进入循环的条件应该是left < right;
最终应该返回left或者right;
Num(int length) = a1 / length + a2 / length + ……
注意，计算mid时，为了防止left=0,right=1时, 此时mid==0进入Num函数导致的除数为0，应该在此加上1再除以2，
而且，若没加上1时，当right = left + 1时，设此时left = x, 那么mid = (left + right) /2会等于left==x, 若此时num(mid) >= k那么left = mid == x, 进入下一个循环又是mid=left==x, mid,left就会一直相等num(mid)结果一直不变导致死循环。
#include <iostream>
using namespace std;
const int MAXN = 1005;
int a[MAXN];//存木棒长度
int n, k;
int Num(int length){int ans = 0;for(int i = 0; i < n; i++)ans += a[i] / length;//注意除法要求除数不为0！！return ans;
}
int binarySearch(int right){int left = 0, mid;while(left < right){mid = (left + right + 1) / 2;if(Num(mid) < k)right = mid - 1;else left = mid;}return left;// or right;
}
int main(){cin >> n >> k;int maxL = 0;for(int i = 0; i < n; i++){cin >> a[i];if(a[i] > maxL)maxL = a[i];}printf("%d\n", binarySearch(maxL));
}
