BOJ 25406 식사 계획 세우기

문제 링크입니다.

불가능한 경우

계획 상에서 인접한 두 식당의 메뉴는 서로 달라야 합니다. 한 메뉴가 무지하게 많다면 그걸 최대한 욱여넣는 방법을 생각해 봐야 합니다.

예를 들어서 1번 메뉴를 파는 식당이 엄청 많다고 해봅시다. 그러면 식사 계획 상에서 메뉴의 배치는 1 x 1 x 1 … 과 같이 1과 다른 값이 번갈아 나타나는 형태여야 합니다. 이때 쓸 수 있는 1의 개수의 최댓값은 전체 식사 계획의 길이의 절반을 올림한 값입니다.

I AM GREEDY

식사 계획을 앞쪽부터 채워나갈 건데, 직전과 같은 메뉴가 오면 안 된다는 제약을 빼면 그냥 비어있는 상황과 같습니다. 즉, 현재 남은 식사 계획의 길이의 절반 이상인 메뉴가 있으면 그 메뉴를 써 줘야 합니다. 그게 아니라면 그냥 사전 순으로 가장 빠른 식장을 가져옵니다. 이때만 직전 식당과 같은지 확인해 주면 됩니다.

식사 계획을 세우는 게 가능하다면 각 메뉴는 아무리 많아봤자 식사 계획 길이의 절반을 올림한 개수 이하입니다. 이는 남은 식당의 절반 이상이기 때문에, 남은 식당이 홀 수 개면 존재한다면 유일하고, 짝수 개면 최대 2개까지 존재할 수 있습니다.

두 경우는 각각 그때그때 번갈아가면서 절반 이상인 메뉴와 다른 메뉴를 계획에 추가하는 것으로 해결되므로, 이상의 전략이 유효합니다.

정렬성을 유지하는 우선순위 큐 등의 자료 구조를 이용하면 그때그때 가장 수가 많은 메뉴와 가장 사전 순으로 빠른 번호의 식당을 찾아낼 수 있습니다.

코드

대회 때 짠 코드라 좀 더럽네요.

#include <bits/stdc++.h>
using namespace std;
vector< queue<int> > v;
int plan[321098];
int num[321098];
int a[321098];
int cntfromsize[321098];
int cntfromnumber[321098];
int n;

struct rest{
	int idx, minnum, size;
	friend bool operator<(const rest& a, const rest& b){
		if(a.size == b.size){
		  return a.minnum > b.minnum;
		}
		return a.size < b.size;
	}
};

struct Rest{
	int idx, minnum, size;
	friend bool operator<(const Rest& a, const Rest& b){
		if(a.minnum == b.minnum){
			return a.size < b.size;
		}
		return a.minnum > b.minnum;
	}
};

priority_queue<rest> pq_by_size;
priority_queue<Rest> pq_by_number;

int main() {
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	v.resize(n+1);
	int m = -1;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		v[a[i]].push(i);
		num[a[i]]++;
		if(num[a[i]] > m) m = num[a[i]];
	}
	if(n%2){
		if(m > n/2+1) return !(cout << -1);
	}
	else{
		if(m > n/2) return !(cout << -1);
	}
	for(int i = 1; i <= n; i++){
		if(num[i]){
			rest r;
			Rest R;
			r.idx = R.idx = i;
			r.minnum = R.minnum = v[i].front();
			r.size = R.size = num[i];
			pq_by_size.push(r);
			pq_by_number.push(R);
		}
	}

	int lastidx = 0;
	rest remain;
	Rest Remain;
	bool re = false;
	bool Re = false;
	for(int i = n; i > 0; i--){
		int t = pq_by_size.top().size;
		if((t >= i/2+i%2 && i%2 == 1) || (t > i/2 && t%2 == 0)){
			rest p = pq_by_size.top();
			pq_by_size.pop();
			if(cntfromnumber[p.idx]){
				p.minnum = v[p.idx].front();
				p.size -= cntfromnumber[p.idx];
				cntfromnumber[p.idx] = 0;
				if(p.size > 0) pq_by_size.push(p);
				i++;
				continue;
			}
			else if(lastidx == p.idx){
				re = true;
				remain = p;
				i++;
				continue;
			}
			else{
				cout << p.minnum << ' ';
				v[p.idx].pop();
				p.minnum = v[p.idx].front();
				p.size--;
				lastidx = p.idx;
				if(p.size > 0) pq_by_size.push(p);
				cntfromsize[p.idx]++;
			}
		}

		else{
		   Rest p = pq_by_number.top();
			pq_by_number.pop();
			if(cntfromsize[p.idx]){
				p.minnum = v[p.idx].front();
				p.size -= cntfromsize[p.idx];
				cntfromsize[p.idx] = 0;
				if(p.size > 0) pq_by_number.push(p);
				i++;
				continue;
			}
			else if(lastidx == p.idx){
				Re = true;
				Remain = p;
				i++;
				continue;
			}
			else{
				cout << p.minnum << ' ';
				v[p.idx].pop();
				p.minnum = v[p.idx].front();
				p.size--;
				lastidx = p.idx;
				if(p.size > 0) pq_by_number.push(p);
				cntfromnumber[p.idx]++;
			}
		}
		if(re) pq_by_size.push(remain);
		if(Re) pq_by_number.push(Remain);
		re = Re = false;
	}
}