Link: http://tioj.ck.tp.edu.tw/problems/1332
用map(也可用set包pair)隨便亂寫AC，插入的時候用map找比它大和比它小的兩數分別是誰，誰比較晚插入誰就是它的爸爸。
複雜度O(nlgn)，據說正解是用笛卡爾樹O(n)，參考:
http://ckhs1328.pixnet.net/blog/post/40525136-tioj-1332-%E5%90%8D%E7%BE%A9%E8%80%81%E7%88%B8
http://cbdcoding.blogspot.tw/2015/03/tioj-1332.html
AC code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
using namespace std;
int ans[1000010];
int ()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
map<int,int> st;
st.insert({0,-1});
st.insert({n+1,-2});
for(int i=0;i<n;i++)
{
int t;
cin>>t;
map<int,int>::iterator it1=st.lower_bound(t), it2=it1;
it1--;
if(it1->second > it2->second)
ans[t]=it1->first;
else
ans[t]=it2->first;
st.insert({t,i});
}
for(int i=1;i<=n;i++)
cout<<ans[i]<<'n';
}
|
近期评论