f632 - 渡船頭
題目描述
題目描述了渡船頭的運作方式，給定渡船的營業時間範圍、發船間隔、每次可載客數量，以及乘客的到達時間和小費。目標是計算在營業時間內，船老大可以獲得的最大小費總額，以及載運的總客人數。
解題思路
本題的核心思想是貪婪演算法。首先，將乘客按照到達時間排序。然後，模擬渡船的運作，每隔 K 時間發船一次。每次發船時，從到達時間小於等於當前時間的乘客中，選擇小費最高的 P 個乘客載運。使用優先佇列 (priority queue) 來維護到達時間小於等於當前時間的乘客，並快速找到小費最高的乘客。統計每次發船載運的乘客數量和小費總額，直到營業時間結束。
複雜度分析
- 時間複雜度: O(N log N)，其中 N 是乘客數量。排序需要 O(N log N) 的時間，優先佇列的插入和刪除操作需要 O(log N) 的時間，在迴圈中執行 N 次，因此總時間複雜度為 O(N log N)。
- 空間複雜度: O(N)，優先佇列最多儲存所有乘客，因此空間複雜度為 O(N)。
程式碼
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int t1,t2,k,p,it,ans,ap,xx,yy;
vector <pair<int,int>> a;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t1 >> t2 >> k >> p;
while(cin >> xx >> yy){
a.push_back(make_pair(xx,yy));
++it;
}
sort(a.begin(),a.end());
priority_queue <int> pq;
for(int i=t1,h=0;i<=t2;i+=k){
while(h<it&&a[h].first<=i){
pq.push(a[h].second);
++h;
}
for(int j=0;j<p&&!pq.empty();++j){
ans+=pq.top();
pq.pop();
++ap;
}
}
cout << ap << " " << ans;
}