글 읽기 - 이 문제의 예외케이스를 찾습니다

chickenman 2년 전 0

제가 해본 케이스들입니다

6 3
-6 -2 1 3 8 15

output: 9

2 2
0 1
output: 3

1 2

output: 0

스위핑 알고리즘으로 범위가 겹치는 케이스에 따라서 예외처리를 해보았습니다.

#include <algorithm>
#include <iostream>
using namespace std;

int n, range, ans;
int v[150000];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> range;
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    sort(v, v + n);

    int l = v[0] - range, r = v[0] + range;
    int maxR = v[0] + range;
    bool overlapped = false;

    for (int i = 1; i < n; ++i) {
        int nowL = v[i] - range;
        int nowR = v[i] + range;
        // nowL의 위치에 따라
        // 1. (l, r]
        // 2. (r, maxR)
        // 3. maxR 이상

        if (l < nowL && nowL <= r) {
            if (!overlapped) {
                l = nowL;
                overlapped = true;
            }
            r = maxR;
            maxR = nowR;
        } else if (r < nowL && nowL <= maxR) {
            ans += r - l;
            l = nowL;
            r = maxR;
            maxR = nowR;
        } else {
            if (overlapped) {
                ans += r - l;
                overlapped = false;
            }
            l = nowL;
            r = nowR;
            maxR = r;
        }
    }

    if (overlapped) {
        ans += r - l;
    }
    cout << ans;
    return 0;
}

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

문제

문제

출처

ICPC

이 문제의 예외케이스를 찾습니다

chickenman 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말