挑剔的H胖胖

时间: 1ms        内存:128M

描述:

最近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

提示:

参考答案(内存最优[1120]):

#include<cstdio>
#include<algorithm>
using namespace std;
struct note
{
    int min;
    int max;
    int c;
};
bool cmp(note n1,note n2)
{
    return n1.c>n2.c;
}
int main()
{
    struct note s[105];
    int i,j,k,m,n,t;
    k=0,j=0;
    int a,b,c;
    scanf("%d %d",&n,&m);
    for(i=0;i<n;i++)
    {
        scanf("%d %d %d",&s[i].min,&s[i].max,&s[i].c);
        k+=s[i].min;
        j+=(s[i].min)*(s[i].c);
    }
    if(m<k)
        printf("-1\n");
    else
    {
    sort(s,s+n,cmp);
    t=m-k;
      for(i=0;i<n;i++)
    {
        if(t>=s[i].max-s[i].min)
        {
            t=t-s[i].max+s[i].min;
            j=j+(s[i].max-s[i].min)*s[i].c;
        }
        else
        {
            j=j+(s[i].c)*t;
            break;
        }
    }

         printf("%d\n",j);
    }

       return 0;

    }

参考答案(时间最优[2]):

#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

struct node{
int x,y,z;};
bool cmp(node n1,node n2){

    return n1.z > n2.z;

}
int main()
{
    node items[105];
    int m,n,cnt=0,cnt2=0,res=0;
    cin>>m>>n;
    for(int i=0;i<m;i++){
        cin>>items[i].x>>items[i].y>>items[i].z;
        cnt+=items[i].x;
        cnt2+=items[i].y;
        res+=(items[i].x*items[i].z);
    }
    if(cnt>n){
        cout<<"-1"<<endl;
        return 0;
    }
    n=n-cnt;
    sort(items,items+m,cmp);
    for(int i=0;i<m;i++){
        if(n<=(items[i].y-items[i].x)){
            res+=n*items[i].z;
            break;
        }
        else{
            res+=((items[i].y-items[i].x)*items[i].z);
            n=n-(items[i].y-items[i].x);
        }
    }
    cout<<res<<endl;
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。