题解 P1964 【【mc生存】卖东西】

叫我DJ · 2018-07-27 16:22:21 · 题解

第一篇题解，有点小激动，大佬勿喷 其实这题一点也不坑，数据也很小，所以不用DP，就小小的处理下，排下序就可以过了 话不多说，上代码

#include<iostream>
using namespace std;
struct hgrufdhg {//见题意
    int a;
    int b;
    int c;
    string name;
} th[1001];//要联系后文，分裂物品，所以要开大点（虽然好像题目数据并没有这么坑）
int n,m,ans,i,o;
int main() {
    cin>>m>>n;
    m=21-m;//计算空的格子
    for(i=1; i<=n; i++)
        cin>>th[i].a>>th[i].b>>th[i].c>>th[i].name;//输入不说话
    for(i=1; i<n; i++) {//接下来是一节废话，题目不坑所以没关系
        /*o=1;
        while(th[i].a>th[i].c) {     //介个循环，是处理某一物品数量超过单格数量限制
            th[n+o]=th[i];      //不过数据很人性化，没有这个坑
            th[n+o].a=th[i].c;
            th[i].a-=th[i].c;
            o++;          //在末尾新建一种物体，用来放置该物品多出来的部分
        }
        n+=o;
        n--;*/           //更新n的值
        for(o=i+1; o<=n; o++) {
            if(th[i].name==th[o].name) {//合并同样的物品
                if(th[i].a+th[o].a>th[i].c) {//如果合并后的数量超过单格上限，就用一个个中的物品把另一个填满
                    th[o].a+=th[i].a;
                    th[o].a-=th[i].c;
                    th[i].a=th[i].c;
                } else {//不会超出上限，就直接合并好了
                    th[i].a+=th[o].a;
                    th[o].a=0;
                }
            }
        }
    }
    for(i=1; i<=n; i++)
        th[i].b*=th[i].a;//算出每个格子可以卖多少钱
    for(i=1; i<=n; i++)//数据量少，冒泡就够了
        for(o=i+1; o<=n; o++) {
            if(th[i].b<th[o].b) {
                th[0]=th[i];
                th[i]=th[o];
                th[o]=th[0];
            }
        }
    i=1;
    while(m--) {
        ans+=th[i++].b;//挑出可以卖的最赚钱的几个格子
    }
    cout<<ans;//华丽的输出
    return 0;
}