浙江大学PAT甲級A 1074題解(C++)(1)

#include <iostream>
#include <map>
#include <cstdio>

using namespace std;
int main() {
    int first,n,k;
    cin>>first>>n>>k;
//    int temp;
    int temp, data[100005], next[100005], list[100005], result[100005];
    int sum =0;
    for(int i=0;i<n;i++){
        cin>>temp;
        cin>>data[temp]>>next[temp];
    }

    while (first!=-1){
        //list           
        list[sum++]=first;
        first = next[first];
    }
    for(int i=0;i<sum;i++){
        result[i] = list[i];
    }
    for(int i=0;i<(sum-sum%k);i++){
        result[i] = list[((i/k)*2+1)*k-1-i];
           
    }
    for (int i = 0; i < sum - 1; i++) {
        printf("%05d %d %05d
", result[i], data[result[i]], result[i + 1]);
    }
    printf("%05d %d -1", result[sum - 1], data[result[sum - 1]]);
    return 0;



}

以下、このアルゴリズムの真髄result[i]=list[((i/k)*2+1)*k-1-i]を詳細に説明する.2つの配列の下付きi,xを設定します.i+x=k-1である.i+x=3k-1;i+x=5 k-1...i+x=nk-1は明らか!n=2(i/k)+1(i/k=0,n=1;i/k=1,n=3)x=((i/k)*2+1)*k-1-iここでxはresult[x]であり、ここでの値はlist対応位置の値に置き換えられる