글 읽기 - 파라메트릭서치 관련 질문 (해답 코드가 들어있습니다. 푸신 분만 들어와주세요)

al7ech 4년 전 0

7469번에서 머지소트 트리를 만든 후 1e9 범위에서 파라사메트릭 서치를 돌렸습니다.

처음에 윗 부분의 이진탐색 코드를 제출해서 제출했더니 시간초과가 나왔습니다.

결국 아래 코드를 제출해 정답을 받긴 했는데 아직 윗 부분의 코드가 어떤 부분에서 틀렸는지 잘 모르겠어서 질문드립니다.

감사합니다.

while (L < R)
{
    M = (L + R) / 2;
    if (query(1, 0, N - 1) < K)
        L = M + 1;
    else
        R = M;
}
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
while (L <= R)
{
    M = (L + R) / 2;
    if (query(1, 0, N - 1) < K)
        L = M + 1;
    else
        R = M - 1;
}

djm03178 4년 전 0

R이 L + 1일 때 query의 반환값이 K 이상이면 둘 다 값이 안 변하게 됩니다.

하지만 전체 코드가 없어서 실제로 코드가 어떻게 구성되어 있는지는 모르니 정확한 원인은 모릅니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파라메트릭서치 관련 질문 (해답 코드가 들어있습니다. 푸신 분만 들어와주세요)

al7ech 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말