PAT甲级真题1074
思路来源
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int e[N], ne[N];
int reverse(int head, int k) {
int rear = ne[head];
int PL = ne[head];
int PR = ne[PL];
for (int i = 0; i < k - 1; i ++) {
int t = ne[PR];
ne[PR] = PL;
PL = PR;
PR = t;
}
ne[head] = PL;
ne[rear] = PR;
return rear;
}
int main() {
int head = N - 1;
int h, n, k;
cin >> h >> n >> k;
ne[head] = h;
int addr, data, nextAddr;
for (int i = 0; i < n; i ++) {
cin >> addr >> data >> nextAddr;
e[addr] = data;
ne[addr] = nextAddr;
}
int cnt = 0;
for (int i = ne[head]; i != -1; i = ne[i]) cnt ++;
n = cnt;
int p = head;
for (int i = 0; i + k <= n; i += k) p = reverse(p, k);
for (int i = ne[head]; i != -1; i = ne[i]) {
printf("%05d %d ", i, e[i]);
if (ne[i] != -1)
printf("%05d\n", ne[i]);
else
printf("-1\n");
}
return 0;
}
stl版
using namespace std;
const int N = 100010;
int e[N], ne[N], link[N];
int main() {
int head = N - 1;
int h, n, k;
cin >> h >> n >> k;
ne[head] = h;
int addr, data, nextAddr; //使用一个link数组存储address,利用stl中的reverse函数翻转
for (int i = 0; i < n; i ++) {
cin >> addr >> data >> nextAddr;
e[addr] = data;
ne[addr] = nextAddr;
}
int cnt = 0;
for (int i = ne[head]; i != -1; i = ne[i]) {
link[cnt ++] = i;
}
n = cnt;
int p = head;
for (int i = 0; i + k <= n; i += k) reverse(link + i, link + i + k);
for (int i = 0; i < n; i ++) {
if (i < n - 1)
printf("%05d %d %05d\n", link[i], e[link[i]], link[i + 1]);
else
printf("%05d %d -1\n", link[i], e[link[i]]);
}
return 0;
}