글 읽기 - 어디서 틀렸는지 알 수 있을까요 ?? (C++)

sy46 2년 전 0

더 좋은 접근 방법이나 반례 알려주시면 감사하겠습니다.

#include <iostream>
#include <queue>
using namespace std;
typedef pair<int,int>p;
int arr[100001]; // 자리를 이용한 횟수 저장
bool visit[100001]; // 자리가 비어있는지 확인(true == 사용중, false == 빈자리)
priority_queue<p, vector<p>, greater<p>>q, ans;
priority_queue<int, vector<int>, greater<int>>qls; // 빈 좌석을 빠른 번호 순으로 저장하는 큐
int main() {
	int n, s, e, seat = 0, cnt = 1;
	cin >> n;
	while(n--){
		cin >> s >> e;
		q.push({s,e}); // 이용시간이 빠른 순서로 저장
	}
	arr[0]=1;
	visit[0]=true; // 첫 번째 자리는 사용중
	ans.push({q.top().second, 0}); //ans에 가장 먼저 들어올 사람의 끝나는 시간과 자리 번호 저장
	q.pop();
	while(!q.empty()){
		if(q.top().first < ans.top().first){ // 만약 끝나는 시간이 가장 빠른 사람의 시간보다 들어올 사람의 시간이 더 빠르다면
			if(qls.empty()){ // 만약 이용했던 좌석 중에 빈 공간이 없다면
				seat++; // 새로운 좌석 할당
				arr[seat]++;
				visit[seat]=true; // 새로운 좌석 사용중
				ans.push({q.top().second, seat});
			}
			else{ // 이용했던 좌석중에 빈 공간이 있다면
				visit[qls.top()]=true; // 이용했던 좌석 중 가장 번호가 빠른 좌석 사용
				arr[qls.top()]++; 
				ans.push({q.top().second, qls.top()});
				qls.pop();
			}
		}
		else{
			int t = ans.top().second;
			while(!ans.empty() && ans.top().first <= q.top().first){ // 들어올 사람의 시간보다 더 먼저 끝나는 사람들의 끝나는 시간을 전부 제거
				if(visit[ans.top().second]){ 
					visit[ans.top().second]=false; // 만약 먼저 끝나는 자리가 있으면 빈 자리로 만듦
					qls.push(ans.top().second); // 해당 좌석의 번호를 빈 좌석으로 저장
				}
				t=min(t,ans.top().second); // 빈 자리 중 번호가 가장 빠른 좌석의 번호 저장
				ans.pop();
			}
			ans.push({q.top().second, t});
			visit[t]=true; // 해당 좌석을 사용중으로 변경
			qls.pop(); // 가장 빠른 번호의 좌석이 더 이상 비어있지 않음
			arr[t]++;
		}
		q.pop();
		cnt = max(cnt, (int)ans.size());
	}
	cout << cnt << "\n";
	for(int i=0; i<cnt; i++){
		cout << arr[i] << " ";
	}
}

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

문제

문제

출처

ICPC

어디서 틀렸는지 알 수 있을까요 ?? (C++)

sy46 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말