自动搬运

查看原文

来自洛谷，原作者为

	叫我DJ 这个家伙很勤快，但还是什么也没有留下

搬运于2025-08-24 21:32:23，当前版本为作者最后更新于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;
}