二分、三分、01分数规划
二分查找
单调函数求零点
二分查找：在一个单调有序的集合中查找元素，每次将集合分为左右两个部分，判断解在哪个部分中并调整集合上下界，重复直到找到目标元素。
//找>=x的第一个位置
//求最小值
int l=0,r=ll,mid;
while(l<r)
{
mid=l+(r-l>>1); //(l+r)/2
if(judge(mid)) r=mid;
else l=mid+1;
}
//逐渐减小
cout<<r<<endl;
//在r的位置
//最小值尽量大
//找<=x的最后一个位置
//求最大值
int l=0,r=ll,mid;
while(l<r)
{
mid=l+(r-l+1>>1); //(l+r+1)/2
if(judge(mid)) l=mid;
else r=mid-1;
}
//逐渐扩大
cout<<l<<endl;
//在l的位置
//最大值尽量小
//a[mid]<=x 为需要满足的条件
STL 二分查找函数
#include <algorithm>
binary_search //返回bool值，是否存在
lower_bound //返回可插入的最小位置的迭代器，即返回第一个符合条件的元素位置
upper_bound //返回可插入的最大位置的迭代器，即返回最后一个符合条件的元素位置
//返回的迭代器是指针类型 用返回的迭代器减去a就能得到下标
upper_bound(a,a+10,55)
//1 2 3 3 5 6 9
//插入3，在4这个位置，可插入的最大位置
二分答案+检验
二分枚举+检验：将求解类问题转化为验证类问题
假设距离最近的两个牛棚间的距离为x，牛棚坐标为xi , 先把xi 排序，对于一个解m，验证是否可行，在第一个点放置一头牛，从左向右O(n) 扫描一遍牛棚，第i个点如果和上一个放置点的距离>=m，就在第i个点防放置一头牛，统计总放置的数量是否>=c
Drying
设某一次二分出的一个值为mid，对于一件ai小于等于mid的衣服直接晾干即可，对于一件ai值大于mid的衣服，最少的用时是用吹风机一段时间，晾干一段时间，设这两段时间为x1和x2，那么有mid=x1+x2，ai<=k*x1+x2，那么x1>=(ai-mid)/(k-1)，所以对(ai-mid)/(k-1)向上取整就是该件衣服的最少用时。把所有吹风机的用时加起来应该<=mid
小于等于mid的衣服直接就晾干
对于大于mid的衣服，用x1的时间晾干，用x2的时间吹干，那么x1+x2<=mid k*x2+x1>=ai
解决最大值最小or最小值最大的常见方法
贪心/二分/动态规划
三分
单峰/单谷函数求最大/最小值
在left和right之间取两个点mid和midmid，假如mid比midmid大，那么波峰就不可能出现在midmid和right之间，不断逼近
01分数规划
有一对物品，每一个物品有一个收益ai，一个代价bi，我们要求每一个方案选k个物品使得所选择的 总ai/总bi 最大
收益/价值最大
类似二分答案 二分出一个x 总ai/总bi>=x 总(ai-x*bi)>=0
int n,k;
struct ty{
int c,v;
ll tmp;
}a[10010];
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i].c>>a[i].v;
int l=0,r=1e8+5,ans=0;
while(l<=r)
{
int mid=l+(r-l>>1);
ll tmp=judge(mid);
if(tmp==-1) r=mid;
else
{
ans=tmp;
l=mid+1;
}
}
bool cmp(ty a,ty b)
{
return a.tmp>b.tmp;
}
ll judge(ll x)
{
for(int i=1;i<=n;i++)
{
a[i].tmp=a[i].v-x*a[i].c;
}
sort(a+1,a+n,cmp);
ll sum=0,v=0,c=0;
for(int i=1;i<=k;i++)
{
sum += a[i].tmp;
v+=a[i].v;
c+=a[i].c;
}
if(sum<0) return -1;
else return v/c;
}