51nod 1257 背包问题 V3

基准时间限制：3 秒空间限制：131072 KB 分值: 80 难度：5级算法题

N个物品的体积为W1，W2......Wn（Wi为整数），与之相对应的价值为P1,P2......Pn（Pi为整数），从中选出K件物品（K <= N)，使得单位体积的价值最大。

Input

第1行：包括2个数N, K(1 <= K <= N <= 50000)

第2 - N + 1行：每行2个数Wi, Pi（1 <= Wi, Pi <= 50000)

Output

输出单位体积的价值（用约分后的分数表示）。

Input示例

Output示例

3/4

一道经典问题，在《挑战程序设计竞赛第2版》143页中有原题，最大化平均值。
刚开始我也是想 按照z=p/w 排序，但是这种贪心有问题的。
想到二分答案。
假设知道答案x
那么我们知到总价值要>=x*k;

Sum(p[i])/Sum(w[i])>=x;
Sum只有K个
那么S
Sum(p[i]>=Sum(w[i】*x);
于是 每次求Sum(p[i]-w[i]*x)>=0;求totx,toty最大

难看的代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define N 211111

struct node

{

    int w,p;

    double c;

}a[N];

int cmp(node a,node b)

{

    return a.c>b.c;

}

int n,k;

ll gcd(ll x,ll y)

{

    if (y==0) return x;

    return gcd(y,x%y);

}

ll ax,ay;

int pan(double xx)

{

    ll x,y;

       x=y=0;

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

    a[i].c=1.0*a[i].p-xx*a[i].w;

    sort(a+1,a+n+1,cmp);

    double sum=0;

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

    {

        sum+=a[i].c;

        x+=a[i].p;

        y+=a[i].w;

    }

    if (sum>=0)

    {

        ax=x;

        ay=y;

        return 1;

    }

    return 0;

}

int main()

{

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

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

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

      double l=0,r=5000000000.0;

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

      {

          double mid=(l+r)*0.5;

          if (pan(mid)) l=mid;

          else r=mid;

      }

      cout<<ax/gcd(ax,ay)<<"/"<<ay/gcd(ax,ay)<<endl;

      return 0;

}

PS:做过的类型题，却忘记怎么解决.根本做了没有用。

的确要反思自己的学习方式了

巴特西

51nod 1257 背包问题 V3

最新文章

热门文章