g421 - PC.分身五河

🔗 前往 ZeroJudge 原題

題目描述

題目描述了士道可以使用分身來同時與多個精靈約會。給定精靈數量 N 和士道數量 K，以及每個精靈約會所需的時間 Ti，要求計算完成所有約會所需的最短時間。士道會按照約會請求表的順序來安排約會。

解題思路

這題可以使用貪心策略來解決。我們可以使用一個最小堆（priority queue）來追蹤每個士道何時可用。一開始，所有士道都在時間 0 可用。對於每個約會請求，我們從最小堆中取出一個可用時間最早的士道，並將該士道分配給該約會。士道的可用時間更新為完成該約會的時間。最後，所有約會完成的時間的最大值就是答案。

複雜度分析

• 時間複雜度: O(N log K)，其中 N 是精靈數量，K 是士道數量。因為我們需要對每個精靈執行一次堆操作（pop 和 push），而堆操作的時間複雜度是 O(log K)。
• 空間複雜度: O(K)，因為我們需要一個大小為 K 的最小堆來存儲每個士道的可用時間。

程式碼

#include <iostream>
#include <queue>
using namespace std;
priority_queue <int,vector <int>,greater <int> > q;
int n,m,k,ans;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=0;i<m;++i){
		q.push(0);
	}
	for(int i=0;i<n;++i){
		cin >> k;
		int tmp=q.top();
		q.pop();
		ans=max(ans,tmp+k);
		q.push(tmp+k);
	}
	cout << ans;
}