【題解】Zerojudge b938 - kevin 愛殺殺

題目連結

題目大意

$n$ 個人排成一列，$q$ 筆操作。每次操作告訴你 $i$，代表編號 $i$ 的人會殺掉排在他後面那個人。如果操作不合法要輸出 "0u0 ...... ?"。

題解

本題是 Linked List 的練習題。對於每個人 $i$，我們維護排在他後面那個人的編號 $nxt[i]$。當編號 $i$ 要殺掉他後面那個人，則排在他後面那個人的編號會改變，也就是 $nxt[i] = nxt[nxt[i]]$。實作時要注意 $i$ 是否先前已經被殺掉，或是 $i$ 後面沒有人，請參考 code。

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	vector<int> nxt(n + 1);
	iota(nxt.begin(), nxt.end(), 1);
	while(q--) {
		int p;
		cin >> p;
		p--;
		if(nxt[p] == -1 || nxt[p] == n) {
			cout << "0u0 ...... ?\n";
		} else {
			cout << nxt[p] + 1 << "\n";
			int q = nxt[p];
			nxt[p] = nxt[q];
			nxt[q] = -1;
		}
	}
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge b938 - kevin 愛殺殺