PAT 사다리 경기 L2 - 022. 체인 리스트 [데이터 구조]

6199 단어 PAT사다리 경기
제목 링크
https://www.patest.cn/contests/gplt/L2-022
사고의 방향
먼저 구조 체 로 모든 노드 정 보 를 저장 한 다음 에 전체 링크 를 샅 샅 이 뒤 져 보 세 요.
그리고 다시 줄 을 서 주세요.
그러나 하나의 구덩이 점 이 효과 적 인 결점 이라는 것 을 주의해 야 한다. 반드시 n 이라는 원인 으로 인해 세 번 째 테스트 점 이 지나 치지 못 한 다 는 뜻 은 바로 N 개의 결점 을 제시 하 는 것 이다. 그러나 이 N 개의 결점 이 모두 하나의 링크 에 있 는 것 은 아니다. 즉, 우 리 는 머리 결점 만 있 는 그 링크 가 필요 하 다 는 것 이다.
출력 만 필요 하기 때문에 다음 주 소 는 다음 주소 의 주 소 를 직접 출력 하면 됩 니 다.
아니 야. 그 러 니까 조작 을 다시 한 번 가리 키 는 거 야.
한참 알 아 봤 는데
AC 코드
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define CLR(a) memset(a, 0, sizeof(a))
#define pb push_back

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair  pll;
typedef pair<string, int> psi;
typedef pair<string, string> pss;

const double PI = 3.14159265358979323846264338327;
const double E = exp(1);
const double eps = 1e-6;

const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 5;
const int MOD = 1e9 + 7;

int pos[maxn];

struct Node
{
    int add;
    int value;
    int next;
}temp;

vector  ans, vis;

map <int, Node> m;

void dfs(int add)
{
    vis.pb(m[add]);
    if (m[add].next != -1)
        dfs(m[add].next);
}

int main()
{
    int ini, n;
    scanf("%d%d", &ini, &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d %d", &temp.add, &temp.value, &temp.next);
        m[temp.add] = temp;
    }
    dfs(ini);
    int l = 0, r = vis.size() - 1;
    while (1)
    {
        if (r < l)  
            break;
        ans.pb(vis[r]);
        r--;
        if (r < l)
            break;
        ans.pb(vis[l]);
        l++;
    }
    n = ans.size() - 1;
    for (int i = 0; i < n; i++)
        printf("%05d %d %05d
"
, ans[i].add, ans[i].value, ans[i + 1].add); printf("%05d %d -1
"
, ans[n].add, ans[n].value); }

좋은 웹페이지 즐겨찾기