글 읽기 - 반례를 찾습니다.

dogdriip 7년 전 0

큐를 이용해서 풀려고 시도했습니다. 큐 안에 길이 d로 커버되는 선들을 유지시키는 식으로 진행하며, 큐 크기의 max를 답으로 출력합니다.

길이가 d보다 큰 선분은 아예 제외시키고, 새로운 선분의 오른쪽과 큐의 front의 왼쪽을 비교해서 d보다 작거나 같으면 큐에 넣고, 아니라면 조건을 만족할 때까지 pop한 후 다시 push하는 식으로 구현했습니다.

예제와 게시판에 있는 테케, 직접 만들어 본 테케까지 다 해 봤는데 맞게 나옵니다만, 채점 시작하자마자 틀리네요.

어느 반례가 있을까요? 미리 감사합니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef DEBUG
        freopen("in.txt", "r", stdin);
    #endif
    
    pll p[100001];
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i].first >> p[i].second;
        if (p[i].first > p[i].second) swap(p[i].first, p[i].second);
    }
    ll d; cin >> d;
    
    sort(p, p + n);

    queue<pll> q;
    
    int max_cnt = (int)q.size();
    for (int i = 0; i < n; i++) {
        if (p[i].second - p[i].first > d) continue;
        
        while (!q.empty() && p[i].second - q.front().first > d) {
            q.pop();
        }
        q.push(p[i]);
        
        max_cnt = max(max_cnt, (int)q.size());
    }
    
    cout << max_cnt << '\n';
    
    return 0;
}

jame0313 7년 전 19

4
1 4
1 4
2 5
3 4
3

ANSWER: 3

OUTPUT: 2

dogdriip 7년 전 0

킹갓재명 충성충성

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

문제

문제

출처

ICPC

반례를 찾습니다.

dogdriip 7년 전 0

jame0313 7년 전 19

dogdriip 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말