挑剔的H胖胖

code

4 年前

挑剔的H胖胖

时间： 1ms 内存：128M

描述：

最近H胖胖可爱吃东西了，既想吃草莓，又想吃菠萝，还想吃肉夹馍，可是他有点挑剔，想吃的任何东西都有一个最小值（本胖胖最少要这些才不会不高兴），当然也有最大值（给本胖胖过多，本胖胖也不会喜欢的），为了使胖胖的心情值最大，请大家帮帮忙。

输入：

现在给出胖胖需要的物品总量N（1<=N<=100）和自身能给的物品总数M（1<=M<=10000），之后N行，每行三个数字k1，k2，k3，k1表示对此物品需要的最小值，k2表示对此物品需求的最大值，k3表示胖胖每得到一个此物品之后的心情值。

输出：

输出H胖胖最大的心情值，若能给的物品总数小于H胖胖要求每件物品最小值之和，则输出-1.

示例输入：

示例输出：

提示：

参考答案（内存最优[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;
}

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