九度题目1399：名侦探柯南

题目1399：名侦探柯南
题目描述：
    柯南又遇到了一个棘手的案子：一个贵族的家里被盗。这个贵族的家里非常有钱，但这家主人的习惯很怪异，他将所有的金银珠宝都磨成

粉装到几个分开的袋子里。由于之前并没有记录，所以主人并不知道这次被盗自己损失了多少钱。几天后，盗窃犯被抓住，但是他身上仅有一

个盗窃时用的包，盗窃走的财产早已经挥霍一空。很显然，盗窃犯一定会使自己偷走的东西的总价值最大，柯南虽然断案如神，但是他却无法

计算出盗窃犯到底盗走了价值多少钱的东西。你能帮帮柯南吗？

输入：

         每组测试数据可能有多组输入，对于每一组输入，
         输入的第一行包括两个整数N(1<=N<=100000)，代表主人所拥有的被磨成粉的珠宝的种类数。以及C(1<=C<=10000000)，代表盗窃犯盗

窃时所用的包的容量。
         接下来的N行，每行包括两个数W(1<=W<=10000000) 以及V(1<=V<=10000000)，分别代表一类珠宝粉的总重量，以及这类珠宝粉的总价

值。

输出：
         输出盗窃犯所盗走物品的总价值。
样例输入：
2 10
4 12
8 16

样例输出：
24提示：
若最后得到的被盗物品的总价值不是整数，请你将答案四舍五入后输出。

//贪心

#include<stdio.h>
#include<algorithm>
using namespace std;
struct node
{
   double weight,value,per;
}a[100010];
double cmp(node x,node y)
{
    if(x.per!=y.per) return x.per>y.per;
}
int main()
{
    int i,n;
    double m,sum;
    while(scanf("%d%lf",&n,&m)!=EOF)
    {
       for(i=0;i<n;i++)
       {
          scanf("%lf%lf",&a[i].weight,&a[i].value);
          a[i].per=a[i].value/a[i].weight;
       }
       sort(a,a+n,cmp);
       /*for(i=0;i<n;i++)
       printf("%.0lf %.0lf %.0lf\n",a[i].weight,a[i].value,a[i].per);*/
       sum=0;
       for(i=0;i<n;i++)
       {
          if(m==0)
          break;
          if(m-a[i].weight>=0)
          {
             m-=a[i].weight;
             sum+=a[i].value;
          }
          else
          if(m-a[i].weight<0&&m>0)
          {
             sum+=m*a[i].per;
             m=0;
          }
       }
       //注意四舍五入的方法
       printf("%d\n",(int)(sum+0.5));
    }
    return 0;
}