Zerojudge c471

題敘

https://zerojudge.tw/ShowProblem?problemid=c471
給定 $n$ 個物品的重量 $w_i$ 與拿取次數 $f_i$
定義拿取物品 $i$ 的花費是其 $f_i$ 乘上在其上方物品的重量總和
求最小的花費總和

想法

對於兩個物品 $i$ $j$，只要 $w_i \times f_j < w_j \times f_i$ ，就將 $i$ 放在 $j$ 前面
所以我們只要將所有物品以這種方式排序就會得到最佳的擺放方式
最後再計算總花費即可求解

Code

//By Koios1143
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
long long n,px[100005],w[100005],f[100005],tot=0;
bool cmp(int i,int j){
	return w[i]*f[j] < w[j]*f[i];
}
int main(){
	IOS
	cin>>n;
	for(int i=0 ; i<n ; i++){
		cin>>w[i];
		px[i]=i;
	}
	for(int i=0 ; i<n ; i++){
		cin>>f[i];
	}
	sort(px,px+n,cmp);
	long long ans=0;
	for(int i=0 ; i<n ; i++){
		ans+=f[px[i]]*tot;
		tot+=w[px[i]];
	}
	cout<<ans<<"\n";
	return 0;
}

複雜度

排序時間複雜度為 $O(nlogn)$
計算花費時間複雜度為 $O(n)$
總時間複雜度為 $O(n+nlogn)$