文章目录
pat甲级1133 1133 Splitting A Linked List (25分)1. 20分代码（最后一个点超时）2.正确代码3.总结
pat甲级1133 1133 Splitting A Linked List (25分)
1. 20分代码（最后一个点超时）
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std
;
struct node
{
int data
;
string next
;
};
unordered_map
<string
,node
> mp
;
vector
<string
> v
[3];
int main()
{
string p
,addr
;
int n
,k
;
cin
>>p
>>n
>>k
;
for(int i
=0;i
<n
;++i
)
{
cin
>>addr
;
cin
>>mp
[addr
].data
>>mp
[addr
].next
;
}
while(p
!="-1")
{
int data
=mp
[p
].data
;
if(data
<0) v
[0].push_back(p
);
else if(data
>=0&&data
<=k
) v
[1].push_back(p
);
else v
[2].push_back(p
);
p
=mp
[p
].next
;
}
bool flag
=true;
for(int i
=0;i
<3;++i
)
{
for(int j
=0;j
<(int)v
[i
].size();++j
)
{
if(flag
) {cout
<<v
[i
][j
]<<' '<<mp
[v
[i
][j
]].data
<<' ';flag
=false;}
else cout
<<v
[i
][j
]<<endl
<<v
[i
][j
]<<' '<<mp
[v
[i
][j
]].data
<<' ';
}
}
cout
<<"-1"<<endl
;
return 0;
}
2.正确代码
日沉云起
3.总结
其实思路完全一样，但这里不需要去重，地址全为正值，unoedered_map每次插入新值复杂度为
(
O
(
s
i
z
e
(
)
)
(O(size())
(O(size()).这一点记住。
