自动搬运

查看原文

来自洛谷，原作者为

	Isonan **

搬运于2025-08-24 21:44:09，当前版本为作者最后更新于2018-08-12 10:21:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题传送门>Here<

我的01分数规划学习笔记>Here<

这题是一道01分数规划问题，二分和判定的方法都比较常规，每次二分$mid$时判断能不能使选出的数之和为负数就可以了。对于要求的满足比率最大的条件下使重量最小，只要双关键字排序以后选择就可以了。在二分时顺便存一下选中的零件，最后输出就好了。

代码如下：

#include <cstdio>
#include <algorithm>

struct point{
	double val;
	int pos,m;
}num[10001];
bool cmp(point a,point b){
	return a.val==b.val ? a.m<b.m : a.val<b.val;
} 
double F[10001],M[10001],l,r,mid;
int n,ans[10001],top,tem[10001],ttop;
bool judge(double u){
	for(int i=0;i<=n;i++)num[i].val=M[i]*u-F[i],num[i].m=M[i],num[i].pos=i;
	std::sort(num+1,num+n+1,cmp);
	ttop=0;
	for(int i=1;num[0].val>0.0&&i<=n;i++)tem[++ttop]=num[i].pos,num[0].val+=num[i].val;
	if(num[0].val>0.0)return 0;
	top=ttop;
	for(int i=1;i<=top;i++)ans[i]=tem[i];
	return 1;
}
int main(){
	scanf("%lf%lf%d",F,M,&n);
	for(int i=1;i<=n;i++)scanf("%lf%lf",F+i,M+i);
	l=0.0,r=10000000.0;
	while(r-l>=0.0001){
		mid=(l+r)/2;
		if(judge(mid))l=mid;
		else r=mid;
	}
	std::sort(ans+1,ans+top+1);
	for(int i=1;i<=top;i++)printf("%d\n",ans[i]);
	if(!top)puts("NONE");
}