AcWing 4277. 区块反转
原题链接
简单
#include <iostream>
#include <algorithm>
#define END -1
using namespace std;
const int N = 1e5 + 10;
// 存放输入数据的数组
int d[N], ne[N];
// 存放链表的数组
int link[N];
int main() {
int h, n, m;
scanf("%d%d%d", &h, &n, &m);
// 读入数据
while(n --) {
int addr, data, next;
scanf("%d%d%d", &addr, &data, &next);
d[addr] = data;
ne[addr] = next;
}
// 重建链表,本题可能有多余节点,需要额外定义一个变量
int cnt = 0;
for(int p = h; p != END; p = ne[p], cnt ++)
link[cnt] = p;
// 逆序链表
reverse(link, link + cnt);
// 分组逆序
for (int i = cnt - 1; i >= 0; i -= m)
reverse(link + max(0, i - m + 1), link + i + 1);
// 输出
for (int i = 0; i < cnt; i ++)
{
int addr = link[i], next = link[i + 1];
printf("%05d %d ", addr, d[addr]);
if (i == cnt - 1) puts("-1");
else printf("%05d\n", next);
}
return 0;
}