i792 - pB. 造橋人，我的超人
題目描述
題目要求計算在固定禮物獲得順序下，最佳木板使用順序所需要付出的最小體力值。體力消耗與禮物總重量和木板長度有關。
解題思路
核心思想是利用貪心策略。為了最小化體力消耗，應該優先使用較短的木板來承載較重的禮物。因此，首先將木板長度進行排序。然後，按照禮物獲得的順序，每次選擇當前可用的最短木板來搭建，並計算體力消耗。每次搭建完木板後，更新禮物總重量。
複雜度分析
- 時間複雜度: O(n log n) (主要來自排序)
- 空間複雜度: O(n) (用於儲存木板長度和禮物重量)
程式碼
#include <bits/stdc++.h>
using namespace std;
long n,k,a[100005],ans,s;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n;
for(int i=0;i<n;++i)
cin >> a[i];
sort(a,a+n);
for(int i=n-1;i>=0;--i){
cin >> k;
ans+=s*a[i];
s+=k;
}
cout << ans;
}