글 읽기 - 저 반례를 찾아 주실 수 있나요??

bangbadak 5년 전 0

도전해보는데 예제는 맞아요.. 근데 틀렸다고하니 반례가 있는데 안 보이네요..

#include<iostream>
using namespace std;
bool second = false;
int M, N, sum, arr[1024], i, j, t, c, arr2[1024];
int main(void)
{
	cin >> M;
	for (i = 0; i < M; i++)
		cin >> arr2[i];
	cin >> N;
	for (i = 0; i < N; i++)
		cin >> arr[i];
	for (i = 0; i < M - 1; i++)
	{
		for (j = 0; j < M - 1; j++)
		{
			if (arr2[j] < arr2[j + 1])
			{
				t = arr2[j];
				arr2[j] = arr2[j + 1];
				arr2[j + 1] = t;
			}
		}
	}
	for (i = 0; i < N - 1; i++)
	{
		for (j = 0; j < N - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				t = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = t;
			}
		}
	}
	i = 0;
	j = 0;
	while (i < M)
	{
		while (arr2[i] - arr[j] >= 0 || second == false)
		{
			arr2[i] -= arr[j];
			c++;
			j++;
			if (arr2[i] - arr[j] <= 0)
				second = true;
			else
				second = false;
		}
		
		i++;
	}
	cout << c;
}

jinsung 5년 전 2

바로 아래 글에 올라온 입력인데 저도 여기서 막히네요.

50
1388 1398 1524 1370 1384 1294 1436 1254 1320 1340 1414 1176 1688 1258 1362 1248 1556 1395 1329 1408 1136 1486 1526 1246 1494 1376 1228 958 1306 1382 1666 1576 1328 1336 1082 1562 1358 1320 1654 1248 1312 1444 1438 1150 1502 1536 1316 1460 1622 1316
1023
28 90 10 26 74 32 78 24 50 108 20 104 58 78 114 18 86 64 116 120 98 14 50 38 42 34 72 92 114 12 64 68 62 128 46 90 82 36 114 96 102 48 72 44 36 78 62 96 128 48 40 30 32 54 90 110 72 98 28 52 32 44 16 64 50 94 40 44 60 72 68 40 32 28 110 126 112 64 78 12 54 82 110 76 56 78 104 90 42 22 102 62 70 38 26 18 50 52 100 38 40 78 88 78 80 78 12 92 64 100 112 100 46 96 58 18 106 42 122 36 84 104 102 80 36 100 42 44 16 52 30 100 102 114 98 94 122 48 24 34 38 12 34 72 98 72 56 16 56 60 114 10 22 124 60 26 92 24 52 116 48 68 68 120 98 22 80 60 26 30 20 98 14 114 80 60 92 24 14 28 28 48 24 108 24 40 74 10 28 122 30 78 108 22 104 18 64 120 32 66 38 116 50 32 114 84 122 112 88 102 18 122 58 24 32 60 30 58 18 106 16 48 52 80 56 16 18 114 16 66 40 34 96 12 46 84 18 16 32 22 14 70 24 102 52 82 118 80 96 20 128 88 18 48 50 50 76 72 14 122 128 112 40 18 98 118 16 128 114 122 80 36 114 84 84 46 92 96 78 116 34 30 64 118 10 28 122 28 118 108 76 34 122 90 22 70 66 120 36 86 10 24 24 110 52 58 66 78 74 12 80 36 28 22 120 110 96 44 62 12 126 114 92 72 12 120 60 54 14 118 80 34 42 24 54 28 10 80 24 120 64 60 66 40 58 50 90 82 96 30 50 58 66 100 82 106 112 48 60 124 50 20 118 70 34 128 108 106 108 40 48 120 32 46 102 98 28 124 28 68 62 124 102 68 78 72 48 24 24 24 70 58 64 126 90 102 56 106 24 44 76 66 60 96 12 26 114 62 22 108 24 76 60 14 126 100 104 68 86 72 38 24 64 66 126 72 52 62 128 10 82 12 52 78 14 30 104 46 76 68 66 52 120 102 72 76 94 96 76 78 78 124 44 32 40 26 48 38 44 76 126 108 62 96 44 100 70 116 114 98 66 48 84 76 52 92 36 50 118 56 76 58 92 42 50 32 116 10 48 50 56 22 110 96 124 32 60 10 82 66 104 44 40 34 74 110 118 62 112 126 18 90 76 120 72 62 52 64 88 16 72 94 80 48 12 118 128 48 110 56 90 110 116 52 72 126 82 56 74 92 16 94 104 120 74 102 64 124 44 90 112 104 14 116 88 56 108 34 64 60 38 26 68 108 102 80 48 68 116 50 22 56 30 22 22 48 102 26 82 102 104 68 26 110 28 78 28 62 82 122 92 42 48 10 38 64 22 94 74 104 20 18 90 124 68 76 50 16 68 84 114 72 14 38 26 128 18 56 126 118 118 100 64 124 40 50 104 38 92 70 64 66 48 68 86 28 64 54 120 38 16 112 100 22 100 44 126 16 58 56 116 40 54 124 48 78 106 80 106 96 42 66 76 66 52 76 106 116 20 22 98 104 108 22 94 82 98 60 24 32 74 122 16 76 122 120 20 66 50 26 42 110 116 54 30 118 20 24 24 44 36 66 116 80 90 84 68 104 52 36 114 48 20 78 28 10 70 78 86 128 34 82 14 114 18 86 12 34 40 122 126 106 12 74 124 88 76 28 98 94 20 26 64 14 126 50 32 20 94 68 58 116 34 92 58 36 116 78 28 28 48 44 118 50 104 96 100 118 94 94 58 126 108 32 96 42 70 56 104 96 36 128 76 42 72 24 96 12 118 78 64 56 68 92 80 106 18 116 32 114 68 80 26 12 10 38 10 102 10 10 72 98 20 30 24 46 96 106 92 28 54 88 78 22 94 36 114 122 124 110 104 68 12 58 90 80 94 86 110 34 70 74 38 120 78 42 104 34 118 64 48 100 98 16 60 16 120 128 94 32 52 88 40 112 56 50 30 24 10 84 52 32 82 86 116 24 60 12 100 96 118 14 54 124 102 88 32 18 92 94 44 124 30 70 112 68 58 80 46 48 46 104 70 56 64 70 114 72 88 128 66 44 110 34 92 98 96 40 12 50 110 90 64 124 78 112 40 124 88 82 128 60 98 96 78 120 38 92 110 96 78 128 58 26 10 108 26 42 18 22 94 18 58 122 28 92 70 20 78 34 18 96 34 28 106 30 78 110 30 46 108 22 12 80 128 54 32 26 26 76 28 18 80 82 12 104 80 46 104 70 36 12 116 42 74 40 44 104 68 128 26 14 18 48 24 116 28 74 18 94 14 120 122 78 104 84 120 42 24 54 64 46 36

jinsung 5년 전 2

답은 1022입니다.

pf7 4년 전 0

가장 긴 파이프에서 가장 짧은 필요한 파이프를 잘라내는 구현으로 보입니다. 그러나 탐욕법이 잘못된 것으로 보입니다.(저도 푸는중입니다)

반례:

Input :

5
15 30 40 51 25

10
15 16 17 18 19 20 21 25 24 30

Output : 7

Expected : 8

51 파이프는 16, 17, 18 로 잘라져야 최대 8개의 파이프를 얻을 수 있으나 올려주신 구현에서는 51파이프를 15,16,17 파이프로 자르게 되어 기존의 길이 15 파이프를 쓰지 않습니다.

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

문제

문제

출처

ICPC

저 반례를 찾아 주실 수 있나요??

bangbadak 5년 전 0

jinsung 5년 전 2

jinsung 5년 전 2

pf7 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말