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