글 읽기 - 10000번 질문있습니다.

plzrun 7년 전 0

일단 아래와 같이 푼다음에,

틀렸다고 하길래 COCI 솔루션보고 테케를 몇개 더 만들어서 비교해봤으나

어디가 틀린건지 정확히 잘 모르겠습니다.

left를 작은순서로 right를 큰 순서대로 뽑아내기 위해서 heap을 사용했어요.

left 소팅되는 부분이 우선순위가 있는부분이구요~ (left가 같으면 right가 큰쪽이 heap의 top()에 있어요)

그럼 힙에서 (l,r)을 뽑았을때 l,r 두 좌표에 대해 체크가 되어있다면 (그니까 if(visited[left] && visited[right]))

그건 큰 원 안에 작은 원들 여러개가 접하는 형태로 들어간 거니까

영역을 위아래 둘로 쪼개면서 조그만 동그라미 영역이 하나 늘어난 거니까 카운트를 2개 늘려줬구요,

아닐때는 1개씩 늘려주도록 했습니다.

답변 주시면 감사하겠음다 :)

#include <iostream>
#include <map>
#include <queue>
using namespace std;
map<int, bool> chk;
struct LR{
    int l, r;
    LR() {}
    LR(int ll, int rr) : l(ll), r(rr) {}
    bool operator<(const LR &rhs) const {
        if(l==rhs.l) return r < rhs.r;
        else return l > rhs.l;
    }
};
priority_queue<LR> h;
int main() {
    ios::sync_with_stdio(false);

    int n,x,r;
    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> x >> r;
        h.push(LR(x-r,x+r));
    }
    int cnt = 1;
    while(!h.empty()) {
        LR t = h.top(); h.pop();
        if(chk.count(t.l)>0) {
            if(chk.count(t.r)>0) cnt+=2;
            else {
                chk[t.r] = true;
                cnt++;
            }
        } else {
            chk[t.l]=chk[t.r]=true;
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}

plzrun 7년 전 1

ainta님이 알려주셨는데요,

4 4

5 1

7 1

이런 경우를 생각하지 못했더라구요 ㅠ

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

문제

문제

출처

ICPC

10000번 질문있습니다.

plzrun 7년 전 0

plzrun 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말