二分查找、三分查找
前言
首先很抱歉因为考完高数还有一堆事儿，再加上我现在正在啃的东西比较难，所以拿之前做过的一个系统性的东西来凑 T^T
“二分查找是一种思想”，这是冬训时师兄的话。个人觉得作为ACMer更重要的是，学了算法和数据结构，能够运用，比如最近张哥发的文章中，有网友提出用二分查找找出窃取照片的人，在个人看来这就是运用啦～哪天个人也能这么聪明就好了 QAQ
Solve It - UVA - 10341
题意
给定p、q、r、s、t，求解给定方程的根
思路
首先要判断单调性，对方程求导，得 -pe^(-x) + qcosx - rsinx + s(secx)^2 + 2xt，把已知条件代入，可得这条式子是恒小于或等于0的，故原方程单调递减，再二分求解即可
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const double eps = 1e-7;
double p, q, r, s, t, u;
double fun(double x) { return p*exp(-x) + q*sin(x) + r*cos(x) + s*tan(x) + t*x*x + u; }
int main(){
while(~scanf("%lf%lf%lf%lf%lf%lf", &p, &q, &r, &s, &t, &u)){
double l = 0, r = 1;
while(fun(l) * fun(r) <= 0 && fabs(fun(l)) > eps){
double mid = (l + r)/2;
if(fun(mid) > 0){
l = mid;
}else{
r = mid;
}
}
if(fabs(fun(l)) < eps){
printf("%.4f\n", l);
}else{
printf("No solution\n");
}
}
}
Pie - POJ 3122
题意
有很多个半径为R1，R2,……，Rn的批萨，现在要分同样大小的批萨（可以不同形状）给M个人，问最大大小能是多少
思路
稍微有点隐晦的二分
对所求的最大大小进行二分，分的人数 >= M 就缩左边界，否则缩右边界
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const double eps = 1e-7;
const double PI = acos(-1);
const int N = 1e4 + 15;
double rr[N];
int main(){
int t;
scanf("%d", &t);
while(t--){
int n, m;
scanf("%d%d", &n, &m);
m++;
for(int i = 0; i < n; i++){
scanf("%lf", &rr[i]);
}
double l = PI/10005.0, r = 10000.0*10000.0*PI;
while(r - l > eps){
int sum = 0;
double mid = (l + r)/2.0;
for(int i = 0; i < n; i++){
sum += (int)(rr[i] * rr[i] * PI/mid);
}
if(sum >= m){
l = mid;
}else{
r = mid;
}
}
printf("%.4f\n", l);
}
}
Trick or Treat - ZOJ 3386
题意
给定N个不同的点，求在x轴上的一点使得所有点到它的距离中的最大值最小
思路
函数叠加，但仍然先递减后递增，故用三分查找的方法找出最小值
#include <iostream>
#include <cstdio>
#include <cmath>
#include <climits>
using namespace std;
const double eps = 1e-5;
const int N = 50005;
double coordinate[N][2] = {0};
double calc(double x1, double y1, double x2, double y2) { return (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2); }
double f(double x, int n){
double ans = calc(coordinate[0][0], coordinate[0][1], x, 0.0);
for(int i = 1; i < n; i++){
ans = max(ans, calc(coordinate[i][0], coordinate[i][1], x, 0.0));
}
return ans;
}
int main(){
int n;
while((~scanf("%d", &n)) && n){
for(int i = 0; i < n; i++){
scanf("%lf%lf", &coordinate[i][0], &coordinate[i][1]);
}
double l = -200000.0;
double r = 200000.0;
while(r - l > eps){
double lm = l + (r - l)/3.0;
double lr = r - (r - l)/3.0;
if(f(lm, n) < f(lr, n)){
r = lr;
}else{
l = lm;
}
}
printf("%.9f %.9f\n", l, sqrt(f(l, n)));
}
}
Trick or Treat - ZOJ 3386
题意
给定N个点，对于每个点给出它的x, y, vx, vy，问这些点何时能取得最大距离的最小值
思路
首先写一下任意两点的距离公式 d^2 = [(xi + t*vxi) - (xj + t*vxj)]^2 + [(yi + t*vyi) - (yj + t*vyj)]^2，该公式可化简，得到二次函数表达式，先递减再递增
既然是二次函数表达式，那么直接叠加，仍然会先递减，后递增，因此用三分查找的方法找出最小值
#include<iostream>
#include<string>
#include<algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 300 + 15;
const double eps = 1e-5;
double x[N], y[N], vx[N], vy[N];
double a[N*N], b[N*N], c[N*N];
inline double twice(double x) {return x*x;}
double getMax(double t, int n){
double ans = 0;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
ans = max(ans, sqrt(twice(x[i] + vx[i]*t - x[j] - vx[j]*t) + twice(y[i] + vy[i]*t - y[j] - vy[j]*t)));
}
}
return ans;
}
int main(){
int t;
int caseno = 1;
scanf("%d", &t);
while(t--){
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%lf%lf%lf%lf", &x[i], &y[i], &vx[i], &vy[i]);
}
double ans = 0;
double l = 0, r = 1e6;
while(r - l > eps){
double lm = (r - l)/3 + l;
double rm = r - (r - l)/3;
double lval = getMax(lm, n);
double rval = getMax(rm, n);
if(lval < rval){
ans = lval;
r = rm;
}else{
ans = rval;
l = lm;
}
}
printf("Case #%d: %.2f %.2f\n", caseno++, l, ans);
}
}
