Infinite Knapsack

传送门

（跟之前某道题很像）

当 \(x\) 无限大时，相当于物品可以选实数个（不拘泥于整数个）。于是很自然地（也是因为价值是一维的，代价是二维的，肯定固定一维不变），把每种物品价值都变为单位 1。

于是我们得到 \(n\) 种物品，每种体积是 \(A’_i,B’_i\)。于是若选了 \(i_1,i_2,…,i_k\) 这些物品，那么最终代价就是

当你有足够的数学敏感度（显然我没有），那么十分容易发现（并不容易），上述表示的就是这 \(k\) 个向量 \((A’_{ik},B’_{ik})\) 构成的多边形（或直线）。

那么易得这个多边形只有下凸壳有用（因为其它点都能被它左下方的点优化）。

所以最终只需要遍历下凸壳（点+线）即可。具体操作为枚举下凸壳上相邻两点。

总时间复杂度 \(O(N\log N)\)

Notice：

memcpy(b,a,a.lenth()*sizeof(type_a));

不加 sizeof 调十年！long double 的 size 竟然高达 36！

Notice：

sort 的比较函数永远不要用 <= >= ，会 RE！！！

#include<bits/stdc++.h>
using namespace std;
#define N 200005
struct node{
	long double a,b,c;
	int typ;
}d[N],p[N];
bool cmp(node x,node y){
	if(x.typ==y.typ){
		if(x.a==y.a)return x.b>y.b;//>=  <
		else return x.a<y.a;
	}
	return x.typ<y.typ;
}
inline bool pd(node i,node j,node k){
	return (j.a-i.a)*(k.b-i.b)-(j.b-i.b)*(k.a-i.a)<=0;
}
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;++i){
		cin>>d[i].a>>d[i].b>>d[i].c;
		d[i].a/=d[i].c;
		d[i].b/=d[i].c;
		d[i].typ=0;
	}
	sort(d+1,d+1+n,cmp);
	int tot=0;
	for(int i=1;i<=n;++i){
		while(tot>1&&pd(p[tot-1],p[tot],d[i]))--tot;
		p[++tot]=d[i];
	}
	memcpy(d,p,(tot+1)*sizeof(node));//sizeof  tot+1
	long double ans=max(d[1].a,d[1].b);
	for(int i=2;i<=tot;++i){
		ans=min(ans,max(d[i].a,d[i].b));
		if(fabs(d[i-1].b-d[i-1].a)<1e-5)continue;
		long double p=(d[i].a-d[i].b)/(d[i-1].b-d[i-1].a);
		if(p>0){//p duo jia l
			ans=min(ans,(d[i].a+p*d[i-1].a)/(1+p));
		}
	}
	ans=1.0/ans;
	cout<<fixed<<setprecision(4)<<ans<<endl;
	return 0;
}

原文地址：http://www.cnblogs.com/Huster-ZHY/p/16856056.html