2022.12.28 PM 09:30 by CBJ
來源 : https://zerojudge.tw/ShowProblem?problemid=c471 出題者 : 2017年10月APCS 標籤 : 貪心法(自定義排序) 難易度 : 5
解題想法 : 一次看整個大問題會很繁瑣,但若將其化為小問題,便能迎刃而解。 題目可以理解成,透過一種排序方式,使得所花的能量最小,因此其實這題就是自定義排序。 怎麼排? 排序的核心操作就是兩兩相比,較好的放前/後面,而這題的好與不好,可以透過觀察得到。 例如有重量為10和重量為20的物品,取用頻率皆為1,此時根據題意很直覺的會知道,應該要是10放上面,20放下面,但若取用頻率變為1和3時,又該怎麼排? 首先分別對兩種情形進行計算,假如10在上,20在下,則需花費10*3=30,而若20在上,10在下,則只要花費20*1=20,得到了跟先前不同的結果。 看到這裡,相信應該可以理解到,重量和頻率都將影響排序結果,而(重量*頻率)較小的,放在上面會是好的,如此一來,我們就完成了這題最難的部分了。 ※小提醒 : C/C++記得要開long long ※小技巧 : Python的多元素排序可以引入functools中的cmp_to_key(),並使用[].sort(key=cmp_to_key(cmp))做排序,其中的cmp()函式需要自己寫,詳細可參考 https://www.gairuo.com/p/python-cmp-to-key (計算答案時會需要取前面幾項的和,可用前綴和實作or輸出時再累加。輸出時累加的方法可見此篇文章的解 : https://yuihuang.com/zj-c471/)
//C++ language
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
bool cmp(pair<LL,LL>a, pair<LL,LL>b){
return a.first*b.second < a.second*b.first;
}
int main(){
int N; cin>>N;
vector<LL>presum(N);
vector<pair<LL,LL>>data(N);
for(int i=0;i<N;i++) cin>>data[i].first;
for(int i=0;i<N;i++) cin>>data[i].second;
sort(data.begin(),data.end(),cmp);
presum[0]=data[0].first;
for(int i=1;i<N;i++) presum[i]=presum[i-1]+data[i].first;
LL cost=0;
for(int i=1;i<N;i++) cost+=data[i].second*presum[i-1];
cout<<cost<<"\n";
return 0;
}

## Python language
from sys import stdin
from functools import cmp_to_key
N=int(input())
w=[0]+[int(x) for x in input().split()]
f=[0]+[int(x) for x in input().split()]
def cmp(a,b): return a[0]*b[1] - a[1]*b[0]
data=list(zip(w,f))
data.sort(key=cmp_to_key(cmp))
presum=[0]
for i in range(1,N+1): presum.append(presum[i-1]+data[i][0])
cost=0
for i in range(2,len(data)):
cost+=data[i][1]*presum[i-1]
print(cost)
