核心思想:用数组模拟链表;二维数组
大致流程,我们将一个一个的块视为一个一个数组,用一个vector包含每个块(块内按链表遍历序存储),输出下一个结点的地址时分情况讨论:
1.当下一个节点是最后一个节点时,记得ne[p]要变成-1。
2.当下一个节点不是最后一个节点,但是下一个块的第一个节点时,记得输出第一个节点的地址,而不是原序。
3.当下一个节点仍在当前块内时,按原链表遍历序输出地址。
CODE:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#define PLL pair<ll,ll>
#define VLL vector<ll>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 100,INF = 0x3f3f3f3f;
ll n,k,ne[N],v[N],h;
VLL ans[N];
inline void read(ll &);
int main()
{
read(h);read(n);read(k);
for(int i = 1;i <= n;++i)
{
ll val,now,next;
read(now);read(val);read(next);
ne[now] = next;
v[now] = val;
}
ll t = 1,sum = 0;
for(int i = h;i != -1;i = ne[i])
{
if(t > k)
{
t = 1;
++sum;
}
ans[sum].push_back(i);
++t;
}
++sum;
reverse(ans,ans + sum);
for(int i = 0;i < sum;++i)
{
for(int j = 0;j < ans[i].size();++j)
{
if(i + 1 == sum && j + 1 == ans[i].size()) printf("%05lld %lld -1\n",ans[i][j],v[ans[i][j]]);
else
{
if(j + 1 == ans[i].size()) printf("%05lld %lld %05lld\n",ans[i][j],v[ans[i][j]],ans[i + 1][0]);
else printf("%05lld %lld %05lld\n",ans[i][j],v[ans[i][j]],ne[ans[i][j]]);
}
}
}
return 0;
}
inline void read(ll &x)
{
x = 0;
ll f = 1;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = x * 10 + (c ^ 48);
c = getchar();
}
x *= f;
return ;
}