1074 reverse list

6599 단어
마지막 테스트 용례는 매우 구덩이이다. 주의해서 제시한 n개의 노드가 반드시 h를 머리로 하는 체인 테이블에 있는 것은 아니다. 이런 테스트 용례는PAT 체인 테이블과 관련된 문제에서 여러 번 나타나므로 주의해야 한다.
AC 코드
#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>
using namespace std;
class node{
public:
    int addr;
    int v;
    int next;
};
int main(){
    int h,n,k;
    scanf("%d %d %d",&h,&n,&k);
    vector<node> list;
    map<int,node> rec;
    for(int i = 0;i < n;i++){
        node tmp;
        scanf("%d %d %d",&tmp.addr,&tmp.v,&tmp.next);
        rec[tmp.addr] = tmp;
    }
    int addr(h);
    int count(0);
    while(addr != -1){
        list.push_back(rec[addr]);
        addr = rec[addr].next;
    }
    n = list.size();
    if(n < k){
        for(int i = 0;i < list.size();i++){
            if(list[i].next != -1)
                printf("%05d %d %05d
",list[i].addr,list[i].v,list[i].next); else printf("%05d %d -1
",list[i].addr,list[i].v); } return 0; } for(int i = 0;i < n / k;i++){ reverse(list.begin() + i * k,list.begin() + (i+1) * k); for(int j = i * k;j < (i+1) * k;j++){ if(j != (i+1) * k - 1) list[j].next = list[j+1].addr; } } for(int i = 0;i < n / k;i++){ if((i+1) * k < n) list[i * k + k - 1].next = list[(i+1) * k].addr; else list[i * k + k - 1].next = -1; } list.back().next = -1; for(int i = 0;i < list.size();i++){ if(list[i].next != -1) printf("%05d %d %05d
",list[i].addr,list[i].v,list[i].next); else printf("%05d %d -1
",list[i].addr,list[i].v); } return 0; }

좋은 웹페이지 즐겨찾기