[TIOJ] 1332. 名義老爸

題目連結:http://tioj.infor.org/problems/1332
可以發現對於每個點的爸爸必定是在他出現前出現過的,且必定是比他大的最小值或比他小的最大值中較後面插入的數,不過詳細的證明我不太會證...如果有大大願意教我一下我洗耳恭聽。
因此就用個map存每個數,因為要快速找到比他大的最小值跟比他小的最大值,所以不妨把值當作key,插入順序當作value,就得到了一個$O(N log N)$的做法了。
不過本題其實還有更快的做法,複雜度可變成$O(N)$,那就是對於這個數列用奇怪的方式(?建出一顆笛卡爾樹,再轉回原數列即可知道答案,雖然你還是會構造出整棵樹,但因為笛卡爾樹有線性的建法,所以複雜度還是$O(N)$
詳細可參考:這篇(我覺得比較好理解在幹嘛) 跟 這篇 有講怎麼線性構造出笛卡爾樹
#include <bits/stdc++.h>
using namespace std;
#define N 1000000

int ans[N+5];
map<int,int> mp;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n;++i){
		int x;cin>>x;
		int l=-1,r=-1,ll,rr;
		auto it = mp.insert({x,i}).first;
		++it;
		if(it!=mp.end()){
			l=it->second;
			ll=it->first;
		}
		--it;
		if(it!=mp.begin()){
			--it;
			r=it->second;
			rr=it->first;
		}
		if(l==-1&&r==-1) ans[x]=0;
		else if(l==-1) ans[x]=rr;
		else if(r==-1) ans[x]=ll;
		else if(r>l) ans[x]=rr;
		else ans[x]=ll;
	}
	for(int i=1;i<=n;++i) cout<<ans[i]<<'\n';
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology