PAT乙级真题：1110 区块反转

【1110 区块反转 　　分值：25　　乙级】

题解：

1.和一般的链表类题目一样，录入数据后先初始化链表，使用一个数组v保存初始化后每个结点的地址

2.使用一个二维数组B[n/k+1][k]，类似区块的意思，B[k]每次存放K个连续结点如B[0]=[4,5,6],B[1]=[1,2,3]，将链表存到区块数组内

3.逆序访问B，将每个元素依次录入到一维数组ans。最后打印ans里的数据即可。

 1 void ex1110(){
 2     int start,n,k;
 3     cin >> start >> n >>k;
 4     int addr,data,next;
 5     map<int,int> mp_data,mp_next;
 6     vector<int> ans;
 7     for(int i=0;i<n;i++){
 8         cin >> addr >> data >> next;
 9         mp_data[addr] = data;
10         mp_next[addr] = next;
11     }
12     int v[n],t=start,idx = 0;   // idx:下标。while循环结束后idx就是表长=v.size()
13     while(t != -1){
14         v[idx ++] = t;      
15         t = mp_next[t];
16     }
17     int d = idx%k;
18     if(d>0){
19         for(int i=idx-d;i<idx;i++){     // 预处理数据，将队尾不满足k条数据的先加到ans里。ans[7,8]
20             ans.push_back(v[i]);
21         }
22         idx = idx-d;        // 然后修改链表长度
23     }
24     int B[n][k],cnt=0,b_idx=0;      // 将链表剩下的元素都加入到二维数组B中，B[n/k][k]，B[[1,2,3],[4,5,6]]
25     for(int i=0;i<idx;i++){
26         B[b_idx][cnt++] = v[i];
27         if(cnt == k && i+1!=idx){
28             b_idx += 1;
29             cnt = 0;
30         }
31     }
32     for(int i=b_idx;i>=0;i--){          // 遍历B，将B中的元素都加到ans中
33         for(auto it:B[i]){              // 用it遍历二维数组B[i]里的每k个元素
34             ans.push_back(it);
35         }
36     }
37     for(int i=0;i<ans.size();i++){
38         printf("%05d %d ",ans[i],mp_data[ans[i]]);
39         if(i+1 == ans.size()){
40             printf("-1\n");
41         }else{printf("%05d\n",ans[i+1]);}
42     }
43 
44 }
45 
46 int main(){
47     ex1110();
48 
49 
50     return 0;
51 }