f347 - 10154: Weights and Measures

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出最多可以疊在一起的烏龜數量，使得每一隻烏龜都能承受其上方所有烏龜的總重量。每隻烏龜都有重量和力量的限制，力量代表其能承受的最大重量。

解題思路

本題可以使用貪心演算法解決。首先，將所有烏龜按照重量由小到大排序。然後，使用一個優先隊列（priority queue）來追蹤目前疊在一起的烏龜，優先隊列按照力量由大到小排序。 遍歷排序後的烏龜列表，對於每一隻烏龜，嘗試將其疊到現有的烏龜塔上。如果該烏龜的力量大於或等於目前烏龜塔的總重量，則將其加入優先隊列，並更新烏龜塔的總重量。 如果該烏龜的力量不足以承受目前烏龜塔的重量，則從優先隊列中移除力量最小的烏龜（即隊列頂部的烏龜），直到該烏龜的力量大於或等於目前烏龜塔的重量，或者優先隊列為空。 在每次迭代中，記錄目前烏龜塔中的烏龜數量，並在遍歷結束後輸出最大值。

複雜度分析

• 時間複雜度: O(n log n)，其中 n 是烏龜的數量。排序需要 O(n log n) 的時間，遍歷烏龜列表需要 O(n) 的時間，優先隊列的插入和刪除操作需要 O(log n) 的時間，總體時間複雜度為 O(n log n)。
• 空間複雜度: O(n)，優先隊列最多可能存儲所有烏龜，因此空間複雜度為 O(n)。

程式碼

#include <bits/stdc++.h>
using namespace std;
long long n,ans,w;
pair <long long,long long> a[5700];// p w
priority_queue <pair <long long,long long>> pq; // w p
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	while(cin >> a[n].second >> a[n].first)++n;
	sort(a,a+n);
	for(int i=0;i<n;++i){
		pq.push({a[i].second,a[i].first});
		w+=a[i].second;
		if(w>a[i].first)w-=pq.top().first,pq.pop();
		ans=max(ans,(long long)pq.size());
	}
	cout << ans << '\n';
}