f832 - 隕石 (Meteorite)
題目描述
題目描述了有 N 顆隕石和 M 個隕石捕捉器。每個捕捉器有容量限制，目標是最大化捕捉到的隕石總重量。
解題思路
本題可以使用貪心演算法解決。首先，將隕石重量和捕捉器容量分別排序。然後，從隕石重量最大的開始，嘗試找到一個容量足夠的捕捉器來捕捉它。如果找到，則將隕石重量加到總重量中，並將該捕捉器標記為已使用。重複此過程，直到所有隕石都被考慮過或所有捕捉器都被使用。
複雜度分析
- 時間複雜度: O(n log n + m log m)，其中 n 是隕石數量，m 是捕捉器數量。排序佔主導地位。
- 空間複雜度: O(n + m)，用於儲存隕石重量和捕捉器容量。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,a[100001],b[100001];
long long int ans;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=0;i<n;++i){
cin >> a[i];
}
for(int i=0;i<m;++i){
cin >> b[i];
}
sort(a,a+n);
sort(b,b+m);
for(int i=n-1,it=m-1;i>=0&&it>=0;--i){
if(a[i]<=b[it]){
ans+=a[i];
--it;
}
}
cout << ans;
}