g504 - 109北二7.消毒殺菌

🔗 前往 ZeroJudge 原題

題目描述

題目描述了在不同時間點噴灑消毒劑，並計算經過指定時間後桌子上的總殺菌力。殺菌力會隨著時間衰減，衰減的公式為 (x - t)，其中 x 是噴灑的殺菌力，t 是經過的時間。目標是計算在首次噴灑後經過 y 單位時間，桌子上剩餘的總殺菌力。

解題思路

這題的核心思想是模擬消毒劑的噴灑和衰減過程。由於需要計算在特定時間點的總殺菌力，並且每次噴灑都會影響後續的殺菌力，因此可以使用優先佇列 (priority queue) 來有效地管理已噴灑的消毒劑。優先佇列按照噴灑時間排序，這樣可以方便地找到最早噴灑的消毒劑，並計算其衰減後的殺菌力。

程式碼的邏輯如下：

1. 讀取噴灑次數 n 和總時間 m。
2. 遍歷每次噴灑，讀取噴灑時間和殺菌力。
3. 對於每次噴灑，首先將優先佇列中所有過期的消毒劑移除（即，噴灑時間小於等於當前時間的消毒劑）。
4. 計算當前噴灑對總殺菌力的貢獻，並更新總殺菌力。
5. 將當前噴灑的殺菌力加入優先佇列。
6. 在所有噴灑完成後，再次移除優先佇列中所有過期的消毒劑，並計算剩餘的總殺菌力。

使用優先佇列的目的是為了在每次噴灑時，快速找到需要移除的過期消毒劑，並計算它們的衰減後的殺菌力。

複雜度分析

• 時間複雜度: O(N log N)，其中 N 是噴灑次數。這是因為每次噴灑都需要在優先佇列中進行插入和刪除操作，而這些操作的時間複雜度都是 O(log N)。
• 空間複雜度: O(N)，因為優先佇列最多會存儲 N 個消毒劑的噴灑時間。

程式碼

#include <iostream>
#include <queue>
using namespace std;
long long n,m,x,y,ans,nt;
priority_queue <long long,vector <long long>,greater <long long> > p;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=0;i<n;++i){
		cin >> x >> y;
		if(i==0)m+=x;
		if(x>m)break;
		while(p.empty()==0&&p.top()<=x){
			ans-=p.size()*(p.top()-nt);
			nt=p.top();
			p.pop();
		}
		ans-=p.size()*(x-nt);
		ans+=y;
		nt=x;
		p.push(x+y);
	}
	//cout << ans << "\n";
	while(p.empty()==0&&p.top()<=m){
		ans-=p.size()*(p.top()-nt);
		nt=p.top();
		p.pop();
	}
	//cout << ans << "\n";
	cout << ans-p.size()*(m-nt);
}