题目描述
最近H胖胖可爱吃东西了，既想吃草莓，又想吃菠萝，还想吃肉夹馍，可是他有点挑剔，想吃的任何东西都有一个最小值（本胖胖最少要这些才不会不高兴），当然也有最大值（给本胖胖过多，本胖胖也不会喜欢的），为了使胖胖的心情值最大，请大家帮帮忙。
输入
现在给出胖胖需要的物品总量N（1<=N<=100）和自身能给的物品总数M（1<=M<=10000），之后N行，每行三个数字k1，k2，k3，k1表示对此物品需要的最小值，k2表示对此物品需求的最大值，k3表示胖胖每得到一个此物品之后的心情值。
输出
输出H胖胖最大的心情值，若能给的物品总数小于H胖胖要求每件物品最小值之和，则输出-1.
样例输入
3 5
1 4 2
1 2 5
2 2 1
样例输出
14
参考代码
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int min;
int max;
int happy;
}
std;
int main()
{
int m,n;
scanf("%d%d",&m,&n);
std a[m];
int i,j;
for (i=0;i<m;i++)
{
scanf("%d %d %d",&a[i].min,&a[i].max,&a[i].happy);
}
for (i=0;i<m-1;i++)
{
int k=i;
for (j=i+1;j<m;j++)
{
if(a[k].happy<a[j].happy)
{
k=j;
}
}
std t=a[k];
a[k]=a[i];
a[i]=t;
}
i=0;
int happya=0;
int now=0;
int minsum=0;
for (i=0;i<m;i++)
{
minsum+=a[i].min;
}
if(minsum>n)
{
printf("-1n");
}else{
n=n-minsum;
int i;
for(i=0;i<m;i++){
a[i].max=a[i].max-a[i].min;
happya+=a[i].happy*a[i].min;
}
i=0;
while(n>0){
if(a[i].max>0&&n>0){
happya+=a[i].happy;
n--;
a[i].max--;
}else{
i++;
}
}
printf("%dn",happya);
}
return 0;
}
解析
暂无
