누군가이 논리로 잘못된 점을 알려주실 수 있습니까?

Question

나는 Hackerrank에 관한 문제를 해결하고 있었다. 다음은 그 질문입니다 (간단히) :

은행을 강탈하려는 강도가있는 n 명의 강도가 있습니다. 그들은 거의 G 분 동안 머물 수 있습니다. 한 번에 두 명의 강도 만 금고에 들어갈 수 있습니다.

a[]={a_1,a_2,...,a_n}는 a_i는i_th강도가 볼트를 유지하고자하는 시간이되도록 사용자가 지정한 배열이다.

강도가 모든 소원을 얻으면 성공합니다.

n,G, a[];출력이 "성공"또는 "실패"해야 감안할 때. 다음과 같이

내 논리였다 : 종류 (A) 순서 는 볼트의 1, 2 사람을 위해 슬롯 1과 슬롯 2를 정의 내림차순으로 각각 슬롯 1 = 슬롯 2 = G 는 A, 이러한 분류에서 슬롯 1과 슬롯 2를 입력 강도가 슬롯에서 끝날 때마다 다음 슬롯이 그의 자리를 차지합니다. 모든 도둑을 수용 할 수 있으면 성공하고 그렇지 않으면 실패합니다.

Answer 1

편집 : 위에서 언급 한대로 JonTheMon은 G = 6 및 a = {2, 2, 2, 3, 3} 일 때 사용자의 접근 방식이 실패합니다.

어쨌든, 당신의 아이디어가 잘못되어 이러한 방식으로 문제를 해결할 수 없습니다. 여기에 힌트가 있습니다 :

이것은 고전적인 DP 문제입니다. 잘못된 테스트 케이스와

이전 게시물 :

이 G = 4 및 a[] = {1, 2, 2, 3}을 보자.

귀하의 접근 방식을 이해하는 한, 먼저 강도 a_1 및 a_2를 수용하게됩니다. a_1이 끝나면 a_3을 소개합니다. 그러나 이것은 vault에 충분한 시간이없는 a_4를 남겨 둡니다. 최소한 3 분 안에 들어가기를 원할 때 2 분 밖에 걸리지 않습니다.

Answer 2

두 번 시도해 봅니다. 먼저, 강도가 원하는 시간을 더한 다음 반으로 줄이고 반올림합니다. 그것은 당신의 이상적인 시간입니다. (이 시점에서 강도 중 하나가이 양보다 많거나 적 으면 확인하십시오. 그렇다면 한계입니다.) 그런 다음 강도가 그 시간대에 맞도록하십시오. 당신이 그들을 균등하게 맞출 수 있다면, 당신은 좋습니다. 그렇지 않으면 시간을 늘리고 다시 시도하십시오.