小胖吃肉

女爷i 2022-08-10 09:58 188阅读 0赞

## 小胖吃肉 ##

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

众所周知，小胖非常喜欢吃肉。有一天，小胖发现了很多块肉。由于每一块肉的大小都不一样，并且每一块肉带给小胖的愉悦程度都不一样。但是因为小胖太胖了，所以小胖的妈妈规定小胖最多可以吃x体积的肉。小胖现在来求助于你，想让你找到一个最优的吃肉方式，使得小胖获得的愉悦度最高。

注：小胖可以只吃一块肉的一部分。

## 输入 ##

首先输入一个整数T，代表有T组数据。

接下来的每组数据的第一行输入两个整数n，x。代表小胖发现了n块肉。小胖最多可以吃x体积的肉。

(n<=1000,x<=10000)

接下来的n行，每行输入两个整数a，b。代表这块肉的体积为a，单位体积的这块肉可以给小胖带来b的愉悦度。

(a<=1000,b<=10000)

## 输出 ##

输出小胖最多可以获得的愉悦度为多少。

## 示例输入 ##

1
    2 3
    10 1
    1 3

## 示例输出 ##

## 提示 ##

小胖可以选择吃第二种肉1体积，吃第一种肉2体积，一共可以获得3+1\*2=5的愉悦度

## 来源 ##

## 示例程序 ##

#include<stdio.h>  
    #include<stdlib.h>  
    struct node  
    {  
        int num,data;  
    }a[10000];  
    int cmp(const void *a,const void *b)  
    {  
        return (*(struct node *)b).data>(*(struct node *)a).data?1:-1;  
    }  
    int main()  
    {  
        int i,j,n,m,k,t;  
        scanf("%d",&n);  
        for(i=0;i<n;i++)  
        {  
            scanf("%d %d",&k,&t);  
            for(j=0;j<k;j++)  
                scanf("%d %d",&a[j].num,&a[j].data);  
            qsort(a,k,sizeof(a[0]),cmp);  
            m=0;  
            for(j=0;j<k;)  
            {  
                if(a[j].num>0&&t>0)  
                {  
                    a[j].num--;  
                    m+=a[j].data;  
                    t--;  
                }  
                else  
                    j++;  
            }  
            printf("%d\n",m);  
        }  
    }