b938 - kevin 愛殺殺

🔗 前往 ZeroJudge 原題

題目描述

題目描述一個名為「盲人摸象」的遊戲，其中有 n 個人排成一列，編號從 1 到 n。每次 kevin 會指定一個編號 k 的人，殺掉他後面的人。程式需要輸出每次被殺掉的人的編號。如果指定的人已經死亡、是最後一個人，或者後面沒有人可以殺，則輸出 "0u0 ...... ?"。

解題思路

這題的核心是模擬這個殺人的過程。由於每次殺掉一個人後，隊伍的結構會發生變化，因此使用鏈表來表示隊伍是一個自然的想法。程式使用一個陣列 a 來模擬鏈表，其中 a[i] 表示第 i 個人後面的人的編號。b 陣列用於記錄哪些人已經被殺掉。每次 kevin 指定一個編號 k，程式會檢查 k 是否合法，以及 k 後面的人是否合法。如果合法，則輸出被殺掉的人的編號，並更新鏈表和已死亡陣列。IO 優化是必要的，因為題目中提到 cin, cout 容易 TLE。

複雜度分析

• 時間複雜度: O(m * 1) (實際上接近 O(m)，因為陣列訪問是常數時間)
• 空間複雜度: O(n)

程式碼

#include <iostream> 
using namespace std;
int n,m,a[1000001],k;
bool b[1000001];
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;++i)
		a[i]=i+1;
	a[n]=-1;
	for(int i=0;i<m;++i){
		cin >> k;
		if(b[k]==1||k<1||k>n||b[a[k]]==1||a[k]==-1)
			cout << "0u0 ...... ?\n";
		else{
			cout << a[k] << "\n";
			b[a[k]]=1;
			a[k]=a[a[k]];
		}
	}
}