pat 1052(22)

还有一个case运行超时,不知道在哪…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
/*
正序
逆序
全相同
无效节点(部分无效,全部无效)
乱序
如果根据给出的起始节点的地址无法找到一条链表,则输出“0 起始节点地址”
5 00001
11111 7 -1
00001 5 77777
33333 6 11111
12345 3 33333
22222 4 12345
*/
#include <cstdio>
#include <climits>
#define MAX 100005
typedef struct
{
int data;
int next;
}Lnode;
int main()
{
int N ,s , i , j;
scanf("%d%d" , &N , &s);
int ad , data , next;
Lnode List[MAX];
for(i = 0 ; i < MAX ; ++i)
List[i].data = INT_MAX;
for(i = 0 ; i < N ; ++i)
{
scanf("%d%d%d" , &ad , &data , &next);
List[ad].data = data;
List[ad].next = next;
}
//deal
/*select sort*/
bool flag = true , right = false;
int first = s , first_b = s;
List[100004].next = s;//虚头结点
s = 100004;
for(i = 0 ; i < N ; ++i)
{
int pp = 100004;
s = List[pp].next;
if(s == -1)//解决无效节点
break;
int min = List[s].data , st = s , pre = s;//Attention
for(j = List[s].next ; j != -1 ; )
{
if(List[j].data == INT_MAX)
{
right = true;
break;
}
if(min > List[j].data)
{
min = List[j].data;
st = j;
pp = pre;//记录前驱
if(flag)
{
first = st;
first_b = first;
}
}
pre = j;//记录前驱
j = List[j].next;
}
if(right)
break;
if(!flag)
{
List[first].next = st;
first = st;
}
flag = false;
//缝合断链
List[pp].next = List[st].next;
}
if(i)
{
printf("%d %05d\n" , i , first_b);
for(i = first_b ; i != -1 ; i = List[i].next)
{
if(List[i].next < 0)
printf("%05d %d %d\n" , i , List[i].data , List[i].next);
else
printf("%05d %d %05d\n" , i , List[i].data , List[i].next);
}
}
else
printf("0 -1");
return 0;
}

热评文章