自己AC代码:
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int ad;
int data;
int next;
int sq;
}Node;
int cmp1(const void *a,const void *b){
Node *pa=(Node*)a;
Node *pb=(Node*)b;
if(pa->sq<pb->sq)
return -1;
else
return 1;
}
int cmp2(const void *a,const void *b){
Node *pa=(Node*)a;
Node *pb=(Node*)b;
if(pa->sq<pb->sq)
return 1;
else
return -1;
}
void change(Node *a,int n){
int first=a[0].next,i;
for(i=0;i<n-1;i++){
a[i].next=a[i+1].ad;
}
a[i].next=first;
}
int main(){
int fa,n,k,i=0,sq=1,sum=0;
scanf("%d %d %d",&fa,&n,&k);
Node node[100010]={0};
int find;
int x=n;
while(x--){
scanf("%d %d %d",&node[i].ad,&node[i].data,&node[i].next);
if(node[i].ad==fa){
find=node[i].next;
node[i].sq=sq++;
sum++;
}
i++;
}
int j=0;
while(find!=-1){
if(node[j].ad==find){
node[j].sq=sq++;
find=node[j].next;
sum++;
}
j++;
if(j==n)
j=0;
}
qsort(node,n,sizeof(Node),cmp1);
for(int v=0;v<sum/k;v++){
qsort(node+n-sum+v*k,k,sizeof(Node),cmp2);
}
for(int v=0;v<sum/k;v++){
change(node+n-sum+v*k,k);
}
for(int v=n-sum+k-1;v<n;v+=k){
node[v].next=node[v+1].ad;
}
for(int v=n-sum;v<n;v++){
if(v<n-1)
printf("%05d %d %05d\n",node[v].ad,node[v].data,node[v].next);
else
printf("%05d %d -1\n",node[v].ad,node[v].data);
}
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int first, k, n, temp;
cin >> first >> n >> k;
int data[100005], next[100005], list[100005];
for (int i = 0; i < n; i++) {
cin >> temp;
cin >> data[temp] >> next[temp];
}
int sum = 0;//不一定所有的输入的结点都是有用的,加个计数器
while (first != -1) {
list[sum++] = first;
first = next[first];
}
for (int i = 0; i < (sum - sum % k); i += k)
reverse(begin(list) + i, begin(list) + i + k);
for (int i = 0; i < sum - 1; i++)
printf("%05d %d %05d\n", list[i], data[list[i]], list[i + 1]);
printf("%05d %d -1", list[sum - 1], data[list[sum - 1]]);
return 0;
}