j537 - 工廠派遣 (Factory)
題目描述
題目描述一個工廠有 n 個工人，每個工人有兩種能力值，分別是工作能力和薪水。工廠老闆有 m 元預算，需要選擇盡可能多的工人。工人的選擇必須按照工作能力降序排列。目標是找出在預算內可以雇用的最大工人數量。
解題思路
本題可以使用貪心演算法解決。首先，按照工人的工作能力降序排序。然後，從工作能力最強的工人開始，依次檢查是否能夠在預算內雇用該工人。如果可以，則雇用該工人，並從預算中扣除該工人的薪水。否則，如果預算仍然大於 0，則雇用該工人，並將預算設為 0。如果預算為 0，則停止雇用工人。
複雜度分析
- 時間複雜度: O(n log n) (主要來自排序)
- 空間複雜度: O(n) (用於儲存工人資料)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,ans;
pair <int,int> a[355];
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n;
for(int i=0;i<n;++i)
cin >> a[i].first >> a[i].second;
cin >> m;
sort(a,a+n);
for(int i=n-1;i>=0;--i){
if(m>=a[i].second){
m-=a[i].second;
++ans;
}
else{
if(m)++ans;
break;
}
}
cout << ans;
}