c471 - apcs 物品堆疊 (Stacking)
題目描述
題目要求計算將 N 個物品堆疊起來的最小能量消耗。每個物品都有重量 w 和取用次數 f。能量消耗與物品的堆疊順序有關，目標是找到一個堆疊順序，使得總能量消耗最小。能量消耗的計算方式是：對於每個物品 i，其能量消耗等於當前堆疊重量總和乘以該物品的取用次數。
解題思路
本題可以使用貪心演算法解決。核心思想是按照物品的 f/w 比例進行排序。具體來說，我們定義一個比較函數 cmp，如果 x.f * y.w > x.w * y.f，則返回 true，表示 x 應該排在 y 的前面。這樣排序的目的是讓重量較輕且取用次數較多的物品優先堆疊，從而減少總能量消耗。排序後，我們從頭到尾遍歷物品，計算每個物品的能量消耗，並將其加到總能量消耗中。在計算每個物品的能量消耗時，我們需要用到當前的堆疊重量總和。
複雜度分析
- 時間複雜度: O(N log N)
- 空間複雜度: O(N)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
struct p{
long long int f,w;
};
long long int n,ans,sum;
p a[1000001];
bool cmp(p x,p y){
if(x.f*y.w>x.w*y.f){
return 1;
}
return 0;
}
int main (){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n;
for(int i=0;i<n;++i){
cin >> a[i].w;
}
for(int i=0;i<n;++i){
cin >> a[i].f;
}
sort(a,a+n,cmp);
for(int i=0;i<n;++i){
ans+=(sum)*a[i].f;
sum+=a[i].w;
}
cout << ans ;
}