二分、三分、01分数规划【第III弹】

目录

一、三分

例题：

1、最长影子

2、最小圆盘覆盖（三分套三分）

3.传送带

二、01分数规划

理解

 例题：小咪买东西

---

一、三分

 对于单峰单谷函数求最值，在left~right区间内，取两个点（图中mid 和 midmid），然后对于“谷”，函数值 f[mid] > f[midmid] 那么最大值一定在区间mid~midmid 或 left~mid 之间，就可以舍弃区间mid~right了，再以midmid为右端点依次“三分”…… 单谷函数类似。

【当然我们也可以对它的导函数二分处理】（可导）

例题：

1、最长影子

 （用相似三角形）

2、最小圆盘覆盖（三分套三分）

一个平面上有一些点，要求用一个圆盘能覆盖所有点（可以在边缘上可以在圆内），求满足要求的圆的最小半径。

【这个题在某场比赛中有个升级版：圆盘->球，二维->三维】其实这种题是有专门的计算几何算法的（貌似叫“模拟退火算法”？），复杂度更低，但是这里用三分也“无伤大雅”。。

思路：圆心坐标y轴确定时，对x，从一端扫到另一端（左->右/ 右->左），半径是先减后增的，同样的道理，x轴确定时，扫y坐标也是先减后增的。那么问题来了，两次的“最低点” 相同吗？即它们整体上是单点吗？答案：是的。【雨jj 的解释是不管是x轴还是y轴，你在平面内随意画两条直线，它都是符合这个性质的，那么那个最低点就是重合的】

所以就可以 “三分套三分地求x坐标和y坐标”了，同理，球的话，就三个三分套起来。。。

【“ 三分的题考得不是特别多，如果出的话，很有可能就是这种题 ” 】

3.传送带

[SCOI2010]传送带

 来了来了 ，一个 “三分套三分” 的题~

首先题目满足“单谷”（只不过是“一个套一个”），在线段AB上取一点m, CD上取一 n ,设路线A-m-n-D为用时最短。第一个三分（写在主函数里）调用check1(), 三分选m点，check1() 里调用check2()【“套”第二个 三分】选 n点.

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-4;//减小误差 
struct nt{
	double x,y;
}a,b,c,d,m,n;
double p,q,r;
 
double dis(nt a,nt b){
	return sqrt(eps+(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));   //加一个极小值eps减小误差
}

double check2(double x){        //x为C-n长度
	double tp=x/dis(c,d);      //根据 比例 算坐标
	n = {c.x+tp*(d.x-c.x), c.y+tp*(d.y-c.y)};
	return dis(n,m)/r + (dis(c,d)-x)/q;    //前面一个三分已经算出了m点
}   //check2()返回m-n段、n-D段 花费时间

double check1(double x){      //x为A-m长度
	double tp=x/dis(a,b);
	m = {a.x+tp*(b.x-a.x), a.y+tp*(b.y-a.y)};
	double l=0, r=dis(c,d), lm, rm;
	for(int i=0;i<1000;i++){
		lm=l+(r-l)/3, rm=r-(r-l)/3;          //三分的 左“中点” 右“中点”
		if(check2(lm) >= check2(rm)) l=lm;
		else r=rm;
	}
	return x/p+check2(l); //A-m段 + check2()返回时间 ==总时间
}
int main(){
	scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y);
	scanf("%lf %lf %lf",&p,&q,&r);
	double l=0, r=dis(a,b), lm, rm;
	for(int i=0;i<1000;i++){
		lm=l+(r-l)/3, rm=r-(r-l)/3;
		if(check1(lm) >= check1(rm)) l=lm;
		else r=rm;
	}
	printf("%.2f",check1(l));
	return 0;
}

注意：关于eps的减小误差的原因看这篇：浮点数数据误差eps处理（详细解析）_扣子不会飞的博客-CSDN博客_eps 误差

【不加eps过不了qwq】

plus: “神兽” 代码：（皮一下很开心 ^ ^）【就是看上面那题的题解时看到的！】

/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/

二、01分数规划

理解

 思考：

怎么选呢？是选前k个a[i]/b[i]最大的吗？很好！->给反例：200/99 , 403/201 , 2/1 三个数中选两个，按此方法则是（200+403）/(99+201) == 603/300  但是如果选 第一个和第三个数：（200+2） /  (99+1) == 202/100 > 603/300 所以，这是不对的，因为求的是整体的除的结果，虽然403/201 比2/1大，但是它的分母对第一个数的分母来说很大......

我们再来谈谈为什么这个叫“01分数规划”吧~ “01”-> 选还是不选 ，"分数" ->分式形式，“规划”->求最值或是啥的（有规划才能最好嘛是吧...[是不是有点勉强]）

做法：公式变形-> 分式变成移到一边的式子，转化成二分。

 例题：小咪买东西

传送门

 

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int M=1e4+6;
ll n, k, c[M], v[M],a[M];
bool check(ll x){
	ll sum=0;
	for(int i=1;i<=n;i++)a[i]=v[i]-x*c[i];
	sort(a+1,a+1+n);
	for(int i=n;i>n-k;i--)sum+=a[i];
	return sum>=0;
}
void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>c[i]>>v[i];
	ll l=0,r=1e8,mid;
	while(l<r){
		mid=l+r+1>>1;
		if(check(mid))l=mid;
		else r=mid-1;
	}
	cout<<l<<'\n';
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t;cin>>t;
	while(t--)solve();
	return 0;
}