글 읽기 - 반례를 도저히 모르겠습니다.

banana970 2년 전 0

고민 정말 많이했는데... 반례를 못찾겠습니다 ㅠ

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int K, N, x;
	vector <int> V;
	long long start=0;
	int arr[10001]={};
	long long sum = 0;
	long long end = 0;
	cin >> K >> N;
	for (int i = 0; i < K; i++) {
		cin >> arr[i];
		sum += (long long)arr[i];
	}
	end = sum / (long long)N+2;
	
	
	long long cnt = 0;
	long long middle;
	
	while (1) {
		if (start > end) {break; }
		middle = (start + end)/2;
		
		cnt = 0;
		for (int i = 0; i < K; i++) {
			cnt += (long long)arr[i] / middle;
		}
		if (cnt == N) {
			V.push_back(middle);
			start = middle+1;
		}
		else if (cnt < N) {
			end = middle-1;
		}
		else {
			start = middle+1;
		}
	}
	if (V.size() == 0) {
		cout << middle;
	}
	else {
		sort(V.begin(), V.end(), greater<>());
		cout << V[0];
	}
}

jhpark0314 2년 전 0

반례입니다

2 2
5
10
//답으로 5가 나와야하는데 6이 나옵니다

banana970 2년 전 0

5면 총 3개가 나오는거 아닌가요??

chldn323 2년 전 0

문제 다시 읽어보시면 "N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다." 이렇게 써있습니다.

6이면 1개고 6이면 3개니까 5가 맞겠네요.

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

문제

문제

출처

ICPC

반례를 도저히 모르겠습니다.

banana970 2년 전 0

jhpark0314 2년 전 0

banana970 2년 전 0

chldn323 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말