f816 - TOI_y21m4_a02Youtube

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算每天的熱門程度。每天的熱門程度是前幾天討論度的總和，但前幾天的討論度會因為時間的推移而下降。具體來說，第 i 天的熱門程度是前 i 天的討論度，其中第 j 天 (j < i) 的討論度會下降 d[i] 。討論度不會降為負數，最低為 0。

解題思路

本題使用 priority queue (最小堆) 和前綴和的組合來優化計算。

1. 前綴和: 維護一個 sum 變數，表示到目前為止所有討論度的總和。
2. Priority Queue: 使用一個最小堆 ans 來存儲已經計算過的熱門度。
3. 每日計算:
   • 將當天討論度 n (加上前綴和 sum) 加入最小堆 ans。
   • 更新總和 tmp (所有熱門度的總和)。
   • 移除堆頂元素，直到堆頂元素小於當前的前綴和 sum。這樣可以確保堆中存儲的都是有效的熱門度。
   • 計算當天的熱門程度：tmp - ans.size() * sum。

複雜度分析

• 時間複雜度: O(D log D)，其中 D 是天數。這是因為對於每一天，我們最多執行 log D 次堆操作 (push 和 pop)。
• 空間複雜度: O(D)，因為 priority queue 最多存儲 D 個元素。

程式碼

#include <iostream>
#include <queue>
using namespace std;
priority_queue <long long int,vector<long long int>,greater<long long int> > ans;
long long int d,n,s,sum,tmp;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> d;
	for(int i=0;i<d;++i){
		cin >> n >> s;
		if(i)sum+=s;
		n+=sum;
		ans.push(n);
		tmp+=n;
		while(ans.top()<sum){
			tmp-=ans.top();
			ans.pop();
		}
		cout << tmp-ans.size()*sum << "\n";
	}
}