b574 - 進德教育

🔗 前往 ZeroJudge 原題

題目描述

題目描述了進德教育的場景，需要計算在一段時間內，最多有多少學生同時待在行政大樓三樓。輸入包含 K 個事件，每個事件表示一個學生進入 (C=1) 或離開 (C=0) 行政大樓三樓。目標是找出在所有事件發生後，行政大樓三樓最多有多少學生同時存在。

解題思路

這題可以使用貪心演算法和模擬的方法來解決。我們維護一個變數 tmp 來記錄目前在行政大樓三樓的人數。對於每個事件，如果學生進入 (C=1)，則 tmp 加 1；如果學生離開 (C=0)，則 tmp 減 1。在每次事件發生後，我們更新 ans 為 tmp 和 ans 的最大值，以追蹤最多同時在行政大樓三樓的人數。

複雜度分析

• 時間複雜度: O(K)，其中 K 是事件的數量。我們需要遍歷所有事件一次。
• 空間複雜度: O(1)，我們只使用幾個常數大小的變數來記錄目前人數和最大人數。

程式碼

#include <iostream>
using namespace std;
int k,n,m,ans,tmp;
int main(){
	cin >> k;
	while(k--){
		cin >> n >> m;
		if(m)++tmp;
		else --tmp;
		ans=max(tmp,ans);
	}
	cout << ans;
}