Today
54
Total
230,470
Notice
«   2022/05   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        
Archives
관리 메뉴

Joonas' Note

BOJ 2517 - 달리기 본문

알고리즘/문제 풀이

BOJ 2517 - 달리기

joonas 2019. 12. 2. 16:55

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

    문제

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

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

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

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

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

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

    코드

    비슷한 문제


    반응형
    0 Comments
    댓글쓰기 폼