글 읽기 - 반례가 있을까요?

wlsgk0323 5년 전 0

질문검색에서 찾은 테스트케이스들은 모두 결과가 정확히 나왔습니다.

근데 제출하니 틀렸다고 나오는데 혹시 간과한 반례가 있을까요?

#include <stdio.h>
#include <algorithm>

using namespace std;

int N, total;
int budget[10001];
int result[10001];

void Search(int start, int end);

int main() {
    int max = 0;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%d", &budget[i]);
    scanf("%d", &total);

    sort(budget, budget + N);
    Search(budget[0], budget[N - 1]);

    for (int i = 0; i < N; i++) {
        if (max < result[i])
            max = result[i];
    }
    printf("%d\n", max);
    return 0;
}

void Search(int start, int end) {
    int maximum = 0, diff = total;
    while(start <= end) {
        int sum = 0;
        maximum = (start + end) / 2;

        for (int i = 0; i < N; i++) {
            if (budget[i] <= maximum)
                sum += budget[i];
            else
                sum += maximum;
        }
        if ((total - sum) >= 0 && (total - sum) <= diff) {
            diff = total - sum;
            for (int i = 0; i < N; i++) {
                if (budget[i] <= maximum)
                    result[i] = budget[i];
                else
                    result[i] = maximum;
            }
        }
        if ((total - sum) == 0)
            return;
        else if ((total - sum) < 0)
            end = maximum - 1;
        else if ((total - sum) > 0)
            start = maximum + 1;
    }
    return;
}

djm03178 5년 전 5

반례 드립니다.

5
4 4 5 5 2
7
output: 0
correct answer: 1

3
3 2 4
5
output: 0
correct answer: 1

3
4 4 5
6
output: 0
correct answer: 2

wlsgk0323 5년 전 1

감사합니다.

해당 반례를 보고 오류를 찾았습니다.

이분 탐색 시작 값을 최소 예산으로 했었는데 0으로 고치니 해결되었습니다.

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

문제

문제

출처

ICPC

반례가 있을까요?

wlsgk0323 5년 전 0

djm03178 5년 전 5

wlsgk0323 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말