# 課堂練習
# f627: 1. 礦砂採集
https://zerojudge.tw/ShowProblem?problemid=f627
這是一個典型的部分背包問題，
每一次取礦石都取當前剩下性價比 (CP 值) 最高的礦石。
運用 pair 分別紀錄初始重量以及單位重量價值 (CP 值)。
再使用自定比較函式，由高到低排序 CP 值。
當背包還有空間時，就不斷的提取。
#include <bits/stdc++.h> | |
using namespace std; | |
#define pii pair<int,int> | |
bool comp(pii a,pii b){ | |
return a.first>b.first; | |
} | |
int main(){ | |
int n,m,w,p; | |
while(cin >> n >> m) | |
{ | |
vector<pii>v; | |
for(int i=0;i<n;i++){ | |
cin >> w >> p; | |
v.push_back({p,w}); | |
} | |
sort(v.begin(),v.end(),comp); | |
int sum=0; | |
for(int i = 0;i<n;i++) { | |
if (m>v[i].second) { | |
sum += v[i].second*v[i].first; | |
m -= v[i].second; | |
} | |
else{ | |
sum += min(v[i].second,m)*v[i].first; | |
break; | |
} | |
} | |
cout << sum << endl; | |
} | |
return 0; | |
} |
# 延伸練習
# e538: 11389 - The Bus Driver Problem
在一個城市裡，有 n 個巴士司機。有 n 條早晨巴士路線和 n 條傍晚巴士路線。
對於任何駕駛員，如果一天的總路線長度超過 d，則必須在 d 小時後以每小時 r 元支付加班費。
您的任務是為每個巴士司機分配一條早上路線和一條傍晚路線，以使支付的總加班費最小。
每一個巴士司機，配給一條當前剩下最短的早上路線與最長的傍晚路線。
這樣就能使超過 d 的數量最少。
#include <bits/stdc++.h> | |
using namespace std; | |
int main() | |
{ | |
int n,d,r; | |
while(cin>>n>>d>>r &&n&&d&&r){ | |
int day[n],night[n]; | |
for(int i = 0;i<n;i++) | |
cin>>day[i]; | |
for(int i = 0;i<n;i++) | |
cin>>night[i]; | |
sort(day,day+n); | |
sort(night,night+n,greater<int>()); | |
int sum = 0; | |
for(int i = 0;i<n;i++) | |
if(day[i]+night[i]>d) | |
sum+=(day[i]+night[i]-d) *r ; | |
cout<<sum<<endl; | |
} | |
return 0; | |
} |
# f832: 隕石 (Meteorite)
已知 OI 國有 M 個隕石捕捉器，每一個捕捉器只能使用一次，而且只可捕捉一個隕石。
第 i 個捕捉器可以捕捉一個重量不超過 單位重的隕石。
N 顆隕石的重量已由科學家估算出來，重量分別為 。
隕石上稀有物質的含量正比於該隕石的重量，目標是要最大化捕捉隕石的重量總和。
每一個捕捉器都只取小於自己的最大隕石即可。
#include <bits/stdc++.h> | |
using namespace std; | |
#define int long long | |
bool high(int a,int b){ | |
return a>b; | |
} | |
signed main(){ | |
int n,m; | |
int W[100005],C[100005]; | |
cin>>n>>m; | |
for(int i = 0;i<n;i++) | |
cin>>W[i]; | |
for(int i = 0;i<m;i++) | |
cin>>C[i]; | |
sort(W,W+n,high); | |
sort(C,C+m,high); | |
int t = 0,total = 0,i=0; | |
while(i!=m&&t!=n){ | |
if(C[i]>=W[t]){ | |
total+= W[t]; | |
i++,t++; | |
}else if(C[i]<W[t]){ | |
t++; | |
} | |
} | |
cout<<total<<endl; | |
} |
