글 읽기 - 회의실 배정문제라 생각하고 풀었는데 반례를 못찾겠습니다..

pica4500 6년 전 1

1에서 200까지의 구간으로 나누어 회의실에 최대한 많이 배정을 해서 몇번 배정하면 모든팀을 배정할지로 문제를 바꾸어 생각해서 구현하였습니다.

정렬의 기준은 1차 : to의 위치, 2차 : from이 작은것부터(to가 같은것중 길이가 긴것이 앞으로 오게) 정렬하여 카운트하였습니다.

힘드네요...

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

struct RANGE {
	int from;
	int to;
	RANGE(int _f, int _t) : from(_f), to(_t){}
};

bool operator<(RANGE a, RANGE b) {
	if (a.to != b.to) {
		return a.to < b.to;
	}
	else {
		return a.from < b.from;
	}
}

vector<RANGE> list;
vector<bool> chkList;
int num;

void chk(int pos) {
	chkList[pos] = true;
	for (int i = pos + 1; i < num; i++) {
		if (list[i].from > list[pos].to && !chkList[i]) {
			chk(i);
            break;
		}
	}
}


bool isFin() {
	for (int i = 0; i < num; i++) {
		if (!chkList[i]) return false;
	}
	return true;
}
int main() {
	int tc;
	cin >> tc;
	while (tc--) {
		list.clear();
		chkList.clear();
		cin >> num;
		for(int i = 0; i < num; i++) {
			int a, b;
			cin >> a >> b;

			int from, to;
			if (a % 2 == 0) from = a / 2;
			else from = (a + 1) / 2;

			if (b % 2 == 0) to = b / 2;
			else to = (b + 1) / 2;

			list.push_back(RANGE(min(from, to), max(from, to)));
		}
		chkList.resize(list.size(), 0);
		sort(list.begin(), list.end());
		int cnt = 0;
		for (int i = 0; i < num; i++) {
			if (!chkList[i]) {
				cnt++;
				chk(i);
			}
		}
		cout << cnt*10 << endl;
	}
}

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

문제

문제

출처

ICPC

회의실 배정문제라 생각하고 풀었는데 반례를 못찾겠습니다..

pica4500 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말