題目連結: https://zerojudge.tw/ShowProblem?problemid=c471
# 解題思路
依兩兩物品頻率 * 其上重量的值排序
假設 a,b 其上物品的重量為 x，則這些物品的順序，不會影響 (a,b) 或 (b,a) 消耗的能量的計算，所以只要考慮 a,b 順序即可。
- (a,b)-> x * f(a) + (x+w(a)) * f(b) = x(f(a)+f(b)) + w(a).f(b)
- (b,a)-> x * f(b) + (x+w(b)) * f(a) = x(f(a)+f(b)) + w(b).f(a)
- 依兩兩物品 (a,b) 頻率 * 其上重量的值排序 (a.w * b.f < b.w * a.f)
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
struct box{ | |
int w,f; | |
}; | |
bool cmp (box a,box b){ | |
return (a.w*b.f<a.f*b.w); | |
} | |
int main(){ | |
int n; | |
while(cin>>n){ | |
struct box b[n]; | |
for(int i=0;i<n;i++) cin>> b[i].w; | |
for(int i=0;i<n;i++) cin>> b[i].f; | |
sort(b,b+n,cmp); | |
long long int ans=0,sum=b[0].w; | |
for(int i=1;i<n;i++){ | |
ans+=sum*b[i].f; | |
sum+=b[i].w; | |
} | |
cout<<ans<<endl; | |
} | |
} |
