1.1从有序数组中查找某值
//数组长 目标值
int n, k;
int arr[n];
void solve()
{
sort(arr, arr + n);
int fst = -1, lst = n, mid;
while(lst - fst > 1)
{
mid = (fst + lst) / 2;
if(arr[mid] >= k) //解范围(fst,mid]
lst = mid;
else //解范围(mid, lst]
fst = mid;
}
return lst;
//此时 fst + 1 = lst
}STL关于二分的应用
STL
lower_bound(begin, end, key)
//从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字
//找到返回该数字的地址，不存在则返回end。
//通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound(begin, end, key)
//从数组的begin位置到end-1位置二分查找第一个大于num的数字
//找到返回该数字的地址，不存在则返回end。
//通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
lower_bound(begin, end, num, greater<type>())
//从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字
//找到返回该数字的地址，不存在则返回end。
//通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound(begin, end, num, greater<type>())
//从数组的begin位置到end-1位置二分查找第一个小于num的数字
//找到返回该数字的地址，不存在则返回end。
//通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
sort(num, num + 6, cmp);
//按从大到小排序
int posa =lower_bound(num, num + 6, 7, greater<int>()) - num;
//返回数组中第一个小于或等于被查数的值
int posb =upper_bound(num, num + 6, 7, greater<int>()) - num;
//返回数组中第一个小于被查数的值
[模板] 结构体使用CMP SORT 二分 的技巧 (重载) 应用51nod 四个数和为零
1.2假定解并判断是否可行
https://vjudge.net/problem/POJ-1064
大意：切K段长度相同的绳子求最大长度
C(x) = (floor(L/x))的总和是否 >= K
double t;
int n, k;
double arr[MAXN];
bool judge(double x)
{
int ret = 0;
for(int i = 0; i < n; i++) {
ret += floor(arr[i] / x);
}
return ret >= k;
}
int main() {
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++) {
scanf("%lf", &arr[i]);
}
double fst = 0.0, lst = 1010101010.0, mid;
for(int i = 0; i < 100; i++) {
mid = (fst + lst) / 2;
if(judge(mid))
fst = mid;
else
lst = mid;
}
printf("%.2f", floor(fst * 100) / 100);
return 0;
}在无法准确确定结束范围时，可按次数不断逼近 100次可达到10^-30的精度
或使用(lst - fst) > EPS，但EPS不可太小,容易死循环。
1.3最大值最小化
void solve()
{
sort(arr, arr + n);
int fst = 0, lst = INF, mid
while(lst - fst > 1)
{
mid = (fst + lst) / 2;
if(judge(mid))
fst = mid;
else
lst = mid;
}
return fst;
}[二分] [POJ] 2456 Aggressive cows
复杂度大概在 O(n*logn)
1.4最大化平均值
现有n物的重价是W和V,选k物使得单位重量价值最大
double wei[MAXN];
double val[MAXN];
double jud[MAXN];
int n, m;
bool cmp(double a, double b)
{
return a > b;
}
bool judge(double x)
{
for(int i = 0; i < n; i++)
jud[i] = val[i] - x * wei[i];
sort(jud, jud + n, cmp);
double rs = 0;
for(int i = 0; i < m; i++)
rs += jud[i];
return rs >= 0;
}
int main()
{
while(cin>>n>>m)
{
for(int i = 0; i < n; i++)
scanf("%lf%lf", &wei[i], &val[i]);
double fst = 0.0, lst = 1010101010.0, mid;
for(int i = 0; i < 100; i++)
{
mid = (fst + lst) / 2.0;
if(judge(mid))
fst = mid;
else
lst = mid;
}
printf("%.2lf
", lst);
}
return 0;
}
V[0]+V[1]+V[2]+...+V[n-1] n种物品的总价值
X * (W[0]+W[1]+W[2]+...+W[n-1]) 所猜测的单位价值为x时的总价值
V[0] - X*W[0]
V[1] - X*W[1]
V[2] - X*W[2]
......
排序之后取前k种最大的值相加
(V[n-1]+V[n-2]+..V[n-k]) = S1 与 X*(W[n-1]+W[n-2]+...W[n-k]) = S2 相比较
如果S1 >= S2 说明X的值还不够大，S1 < S2,说明X太大了