글 읽기 - 반례좀 찾아주시면 감사하겠습니다.

spearkkk 6년 전 0

질문에 있는 반례와 제가 해본 데이터로는 도저히 찾을 수가 없어

올립니다.

찾아주시면 감사하겠습니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int n;
int k;
vector<int> seq;
int tap[100];

int main() {
	scanf("%d %d", &n, &k);
	fgetc(stdin);

	memset(tap, 0, sizeof(tap));

	for (int i = 0; i < k; ++i) {
		int tmp;
		scanf("%d", &tmp);
		fgetc(stdin);

		seq.push_back(tmp);
	}

	for (int i = 0; i < n; ++i) {
		if (find(tap, tap + n, seq[0]) - tap < n) {
			--i;
		}
		else {
			tap[i] = seq[0];
		}
		seq.erase(seq.begin());
	}

	int rslt = 0;

	while (!seq.empty()) {
		if (find(tap, tap + n, seq[0]) - tap < n) {
			seq.erase(seq.begin());
			continue;
		}

		int flg[100];
		memset(flg, 0, sizeof(flg));

		for (int j = 1; j < n && j < seq.size(); ++j) {
			int idx = find(tap, tap + n, seq[j]) - tap;
			if (idx < n) {
				flg[idx] = 1;
			}
		}

		for (int j = 0; j < n; ++j) {
			if (flg[j] == 0) {
				tap[j] = seq[0];
				seq.erase(seq.begin());
				++rslt;
				break;
			}
		}
	}

	printf("%d\n", rslt);

	return 0;
}

zlzmsrhak 6년 전 2

반례입니다.

1 2 3 -> 1 2 4로 1번이면 가능합니다.

3 8
1 2 3 4 1 1 1 2

spearkkk 6년 전 0

감사합니다. 정말, ㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜ 당신은천사!

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

문제

문제

출처

ICPC

반례좀 찾아주시면 감사하겠습니다.

spearkkk 6년 전 0

zlzmsrhak 6년 전 2

spearkkk 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말