POJ2976 Dropping tests


01分数规划裸题,给出n个物品有a b两个属性,选定n-k个元素,
使$\sum{a_i}/\sum{b_i}$最大

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1050;
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*t;
}
int n,k;
int a[maxn],b[maxn],temp[maxn];
bool pan(double x)
{
    for(int i=1;i<=n;i++) temp[i]=a[i]-x*b[i];
    sort(temp+1,temp+1+n);
    double ans=0;
    for(int i=n;i>=k+1;i--) ans+=temp[i];
    return ans>=0;
}
int main()
{
    while(~scanf("%d%d",&n,&k)&&n)
    {
        memset(a,0,sizeof(a)),memset(b,0,sizeof(b));
        for(int i=1;i<=n;i++) a[i]=read();
        for(int i=1;i<=n;i++) b[i]=read();
        double l=0,r=1;
        while(r-l>1e-6)
        {
            double mid=(l+r)/2;
            if(pan(mid)) l=mid;
            else r=mid;
        }
        printf("%.0lf\n",l*100);
    }
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
POJ3621 Sightseeing Cows POJ3621 Sightseeing Cows
这道题是求最优比率环,使点权和除以边权和最大,二分判断即为存在负环,可以用dfs版的spfa进行判断,注意由于二分答案使用duoble,所以与之相关的变量数组一定要定义为duoble #include<cstdio> #includ
2019-07-05
下一篇 
POJ1734 Sightseeing trip POJ1734 Sightseeing trip
floyd经典应用,求无向图最小环,由于floyd循环k层开始时保存的是$d[i,j]$经过编号最大为k-1的节点的最短路, 于是$min(d[i,j]+a[j,k]+a[k,i])$就是满足由编号不超过k的点构成的并且经过k点的最小环,所
2019-07-05
  目录