SS241012B. 电梯（lift）

liyixin0514 / 2024-10-11 / 原文

SS241012B. 电梯（lift）

题意

你有 $n$ 种货物，每种货物有一个高度 $f$ 和体积 $w$。其中 $w$ 表示体积是 $2^w$。你有一个大小为 $2^m$ 的背包，一个背包的花费是背包物品的最大高度，问使用若干个背包装完物品的最小代价。

思路

膜拜黄队%%%感觉黄队的做法比题解好。

首先一个贪心是如果你已经放入了一个高的物品，剩下的空间你一定想尽量放入一个高度差不多的物品，而不是一个超级矮的物品。因此按高度从大到小枚举物品来做。

部分分数的一个做法是，从高到矮枚举物品，每次放能放下的最高的物品。由于物品体积都是 $2$ 的幂，贪心正确。

考虑体积为 $0$ 的物品，两个 $0$ 会占掉 $1$ 的空间。如果不使用体积为 $0$ 的物品，最小能多出来的空间一定是大小为 $1$，然后就可以塞 $2$ 个 $0$ 进去，因此我们可以把大小为 $0$ 的东西两两捆在一起。根据贪心，最高的和第二高的捆在一起，以此类推。如果最后剩下 $1$ 个 $0$，它就自己变成一捆，大小改成 $1$，因为多出来的 $0$ 的空间已经没有用了，放不下任何东西。然后我们考虑若干个大小为 $1$ 的物品，由于一样的原因，可以把它们两两捆在一起。最后捆成若干捆大小为 $m$ 的东西，然后就可以计算代价了。

复杂度 $O(n \log n)$。因为两个东西捆成一个，所以只会捆 $O(n)$ 次。复杂度瓶颈在于排序。

code

~~荣获第二劣解~~

#include<bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
const int N=5e5+7;
#define isdigit(x) (x>='0'&&x<='9')
template <typename T>
void read(T &x) {
	x=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
}
template <typename T>
void write(T x) {
	static int st[10];
	int top=0;
	do {
		st[top++]=x%10;
		x/=10;
	}while(x);
	while(top) putchar(st[--top]+'0');
}
int n,m;
ll ans;
int c,w,f;
typedef pair<int,int> pii;
#define fi first
#define se second
vector<pii > vec[N];
bool cmp (pii a,pii b) { return a.se > b.se; }
int main() {
	#ifdef LOCAL
	freopen("in.txt","r",stdin);
	freopen("my.out","w",stdout);
	#else
	freopen("lift.in","r",stdin);
	freopen("lift.out","w",stdout);
	#endif
	read(n),read(m);
	rep(i,1,n) {
		read(c),read(w),read(f);
		vec[w].push_back({c,f});
	}
	rep(i,0,m-1) {
		sort(vec[i].begin(),vec[i].end(),cmp);
		bool fl=0;
		for(auto u: vec[i]) {
			if(fl) u.fi--;
			fl=0;
			if(u.fi==0) continue;
			vec[i+1].push_back({((u.fi+1)>>1),u.se});
			if(u.fi&1) fl=1; 
		}
	}
	for(auto u:vec[m]) ans+=1ll*u.fi*u.se;
	write(ans);
}