2017/10/18 物品堆疊

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)

相關文章

分享此文：