寫在前面

• 實現思路
  • 結構體封裝數據
    • 根據order重新排序
    • k區間值迭代翻轉
      • n整除k，則最后地址輸出"-1"
      • 非整除，最后剩余區間，原序輸出。最后地址輸出"-1"
• 題目有難度，區間邊界值、實現方案費時間

測試用例

input:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

ac代碼

#include <iostream>
#include <algorithm>
using namespace std;const int maxn = 100010;
struct Node // 定義靜態鏈表
{int address, data, next;int order;Node(){order = maxn;}
} node[maxn];
bool cmp(Node a, Node b)
{return a.order < b.order;
}
int main()
{int bgin, n, k, address;scanf("%d%d%d", &bgin, &n, &k);  // 存儲地址、節點個數、步長（步驟1）for(int i=0; i<n; i++){scanf("%d", &address);scanf("%d%d", &node[address].data, &node[address].next);node[address].address = address;}int p = bgin, cnt = 0;while(p !=-1 )  // cnt 有效節點個數（步驟2）{node[p].order = cnt++;p = node[p].next;}sort(node, node+maxn, cmp);n = cnt;for(int i=0; i<n/k; i++)  // 枚舉完整的n/k塊{// 第i塊倒序輸出（步驟3）for(int j=(i+1)*k-1; j>i*k; j--)printf("%05d %d %05d\n", node[j].address, node[j].data, node[j-1].address);// 每塊最后一個節點地址處理printf("%05d %d ", node[i*k].address, node[i*k].data);// 非最后一塊，指向下一塊的最后一個節點（步驟4）if(i<n/k-1) printf("%05d\n", node[(i+2)*k-1].address);else  // 最后一塊{if(n%k==0) printf("-1\n");  // 最后一個節點，輸出-1;否則，打印剩余不完整的塊相應節點（步驟5）else{printf("%05d\n", node[(i+1)*k].address);for(int i=n/k*k; i<n; i++){printf("%05d %d ", node[i].address, node[i].data);if(i<n-1) printf("%05d\n", node[i+1].address);else printf("-1\n");}}}}return 0;
}

學習代碼

• 1025. 反轉鏈表 (25).cpp···墻裂推薦···
• 實現思路
  • 3個整型數組，有效節點地址順序lists、節點數據data、下一節點地址next
  • 翻轉地址，打印輸出數據、地址、下一地址即可
  • 根據翻轉后的地址循環打印結果數據
  • 打印最后節點
  • 思想很巧妙,值得學習！

#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;
}

知識點小結

// 區間翻轉函數
reverse(begin(list) + i, begin(list) + i + k);