f627 - 1. 礦砂採集
題目描述
題目要求在給定的礦砂中，選擇哪些礦砂可以最大化總價值。每種礦砂都有其價格和價值，且背包容量有限。
解題思路
本題可以使用貪心演算法解決。首先，按照價值由高到低對礦砂進行排序。然後，從價值最高的礦砂開始，盡可能多地選擇這種礦砂，直到背包容量不足。如果當前礦砂的價格大於背包剩餘容量，則選擇盡可能多的當前礦砂，直到背包被填滿。
複雜度分析
- 時間複雜度: O(n log n) (主要來自排序)
- 空間複雜度: O(n) (用於儲存礦砂資料)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
struct stone{
int p,v;
};
bool cmp(stone x,stone y){
if(x.v>y.v)return 1;
return 0;
}
int main(){
int n,m,ans=0;
cin >> n >> m;
stone a[n];
for(int i=0;i<n;++i)
cin >> a[i].p >> a[i].v;
sort(a,a+n,cmp);
for(int i=0;i<n&&m>0;++i){
if(a[i].p<=m){
ans+=a[i].p*a[i].v;
m-=a[i].p;
}
else{
ans+=a[i].v*m;
m=0;
}
}
cout << ans << "\n";
}