Joonas' Note

Joonas' Note

BOJ 2517 - 달리기 본문

알고리즘/문제 풀이

BOJ 2517 - 달리기

2019. 12. 2. 16:55 joonas

    링크: https://www.acmicpc.net/problem/2517

    문제

    최선의 등수는 다시 말하면, "a[k] = 어떤 k 입장에서 왼쪽으로 자신보다 높은 실력의 개수" 이다.

    "왼쪽으로"의 뜻은 "이전까지 등장한"과 같은 말이고, 자신보다 높은 실력의 개수는 기록을 통해서 셀 수 있다.

    문제는 수의 범위가 1,000,000,000 이하라서 수를 직접 저장하기는 힘들어 보인다.

    문제 조건 중, 참가한 선수들의 실력은 모두 다르다는 조건이 있다. 그럼 같은 의미로 그 사람의 등수를 기록하자.

    N은 50만 이하이므로, 등장한 등수(rank)를 1로 기록하고 k 위치에서 자신보다 높은 실력(=등수)는 세그먼트 트리로 쉽게 셀 수 있다.

    선수 k의 최선의 등수는 query(자신의 등수 + 1, 범위 끝) + 1이다.

    코드

    비슷한 문제


    Comments