LOJ149 0/1分数规划

竟然没有写过分数规划的题解

考前挣扎一发板子（

二分答案k 然后0/1分数规划的方法就是分母乘过去然后贪心解决

注意实数二分的精度一般估计一个次数比较好不然容易出现精度比较误差【惨痛教训

就做完了qwq

//Love and Freedom.

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define inf 20021225

#define ll long long

#define db double

#define mxn 100010

#define eps 1e-6

using namespace std;

int a[mxn],b[mxn];

db d[mxn];

int main()

{

	int n,k;

	scanf("%d%d",&n,&k);

	for(int i=1;i<=n;i++)

		scanf("%d",&a[i]);

	for(int i=1;i<=n;i++)

		scanf("%d",&b[i]);

	db r = 1e11, l = 0;

	for(int i=1;i<=100;i++)

	{

		db mid = (l+r)/2.0;

		for(int j=1;j<=n;j++)

			d[j] = (db)a[j]-b[j]*mid;

		sort(d+1,d+n+1); db tmp = 0;

		for(int j=n;j>n-k;j--)	tmp+=d[j];

		if(tmp>-eps)	l=mid+eps;

		else	r=mid-eps;

	}

	printf("%.4lf\n",l);

	return 0;

}

巴特西

LOJ149 0/1分数规划

最新文章

热门文章