백준 21761 / C++

https://www.acmicpc.net/problem/21761

21761번: 초직사각형

 

[ 풀이 ] 

부피 ABCD에서 한 변을 증가시키면 (A+U)BCD가 된다.

그럼 매번 변화시키면서 1+U/A가 커지도록 해주면 된다. 

그리디하게 매번 A,B,C,D중 제일 큰 U를 뽑아서  1+U/x가 제일 큰걸 매번 뽑아주면 된다.

기존 ABCD에서 이렇게 가장 큰 비율을 매번 곱해줘야 최대가 되는건 자명하다.

그 비율이 1보다 크기 때문에 항상 값이 커지기 때문이다.

매번 제일 큰 뭔가를 뽑고 1번쓰고 버리는건 pq를 써주자.

시간복잡도는 O(N+4KlogN)이 된다. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, k, x[4];
priority_queue<ll>pq[4];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k;
	// A, B, C, D의 처음 값 
	for (int i = 0; i < 4; i++) cin >> x[i];
	// pq[i]: A,B,C,D의 U값 저장 
	for (int i = 0; i < n; i++) {
		char T; ll u;
		cin >> T >> u;
		pq[T - 'A'].push(u);
	}
	while (k--) {
		int idx = -1;
		double temp = -1;
		for (int i = 0; i < 4; i++) {
			if (pq[i].empty())continue;
			// 비율 큰걸 고름 
			double w = (double)pq[i].top() / (double)x[i];
			if (temp < w) {
				temp = w;
				idx = i;
			}
		}
		// 그 선분 업데이트
		x[idx] += pq[idx].top();
		cout << "ABCD"[idx] << " " << pq[idx].top() << '\n';
		pq[idx].pop(); // U값 제거 
	}
}