787
九度题目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;
}
最后更新：2017-04-03 12:56:20