P1964 【mc生存】卖东西

题解

很简单，

暴力

注意一个小点就好

 

 

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<queue>

using namespace std;

typedef long long ll;

inline int read()
{
    int ans=0;
    char last=' ',ch=getchar();
    while(ch<'0'||ch>'9') last=ch,ch=getchar();
    while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
    if(last=='-') ans=-ans;
    return ans;
}

int m,n;
struct node{
    int num,w,v;
    string nam;
}obj[105],yy[105];
int p[105],tot=0,yy_tot=0;

bool cmp1(node x,node y)
{
    if(x.nam ==y.nam ){
        return x.num >y.num ;
    }else return x.nam <y.nam ;
}

int main()
{
    m=read();n=read();
    for(int i=1;i<=n;i++){
        obj[i].num =read();
        obj[i].w =read();
        obj[i].v =read();
        cin>>obj[i].nam ;
    }
    
    sort(obj+1,obj+n+1,cmp1);
    
    for(int i=1;i<=n;i++){
        if(obj[i].nam !=obj[i-1].nam ){
            if(yy[yy_tot].num >0){
                p[++tot]=yy[yy_tot].num *yy[yy_tot].w ;
                yy[yy_tot].num-=yy[yy_tot].num;
            }
            yy_tot++;
            yy[yy_tot].num =obj[i].num ;
            yy[yy_tot].v =obj[i].v ;
            yy[yy_tot].w =obj[i].w ;
        }else{
            yy[yy_tot].num +=obj[i].num ;
        }
        
        if(yy[yy_tot].num >=yy[yy_tot].v ){
            p[++tot]=yy[yy_tot].v*yy[yy_tot].w ;
            yy[yy_tot].num-=yy[yy_tot].v;
        }
        
    }
    if(yy[yy_tot].num >0)
        p[++tot]=yy[yy_tot].num *yy[yy_tot].w ;
    sort(p+1,p+1+tot);
    int ans=0;
    for(int i=tot;i>=tot-(21-m)+1;i--){
        if(i<=0) break;
        ans+=p[i];
    } 
    printf("%d\n",ans);
    
    return 0;
}