f929 - 程式老師的作業

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個長度為 n 的正整數陣列，以及 m 個操作。操作包含將陣列中第一個 0 修改為某值 (push)、將指定索引的元素修改為 0 (erase)、以及查詢陣列中第一個 0 的索引 (get)。如果陣列中沒有 0，get 操作應輸出 -1。

解題思路

這題主要考驗對資料結構的應用。由於需要快速找到第一個 0 的索引，並在陣列中插入和刪除 0 的索引，使用 set 是一個不錯的選擇。set 能夠自動排序，並且提供快速的插入、刪除和查找操作。

程式碼首先讀取陣列長度 n，然後讀取陣列元素，將所有 0 的索引存儲到 set 中。接著，讀取操作數量 m，並根據操作類型執行相應的操作。

• push x: 將陣列中第一個 0 修改為 x。如果 set 不為空，則插入新的 0 的索引。
• erase x: 將索引為 x 的元素修改為 0。如果索引 x 存在，則從 set 中刪除。
• get: 輸出陣列中第一個 0 的索引。如果 set 不為空，則輸出 set 中的最小元素（即第一個 0 的索引）；否則，輸出 -1。

複雜度分析

• 時間複雜度: O(m log n)，其中 m 是操作數量，n 是陣列長度。set 的插入、刪除和查找操作的時間複雜度都是 O(log n)。
• 空間複雜度: O(n)，set 最多可能存儲 n 個 0 的索引。

程式碼

#include <iostream>
#include <set>
using namespace std;
int n,m,a,is;
set <int> ss;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0;i<n;++i){
		cin >> a;
		if(a==0)
			ss.insert(i);
	}
	cin >> m;
	while(m--){
		cin >> is;
		if(is==3){
			if(ss.size()==0)
				cout << "-1\n";
			else
				cout << *ss.begin() << "\n";
		}
		else if(is==2){
			cin >> a;
			ss.insert(a);
		}
		else if(is==1){
			cin >> a;
			if(a&&ss.size())
				ss.erase(ss.begin());
		}
	}
}