BOJ 15590 - Rental Service (usaco silver, 그리디, 구간합배열, 이분탐색)

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

 

그리디 + 이분탐색 + 구간합배열로 풀었다.

 

생각한 순서는

1. 모든 소 N마리에 대해 i번쨰 소를 우유를 팔거나, 빌려주거나 하는 완탐 -> (O(2^1000000) 시간초과

 

2. 소의 우유 산출량을 내림차순 정렬한 후, 0~i번째 소는 우유를 팔기로 한다면, i+1~n-1번쨰 소는 반드시 빌려줘야 한다. 

 

빌려주는 경우는 간단하게 처음부터 더해주면 되기 떄문에 그에 맞는 구간합배열을 저장해 뒀다면 상수시간에 도출할 수 있다. 

 

문제는 0~i번째 소의 우유를 팔때의 수익을 반환하는 함수의 논리이다. 그냥 앞에서부터 긁어주면 O(i)로 할 수 있는데, 이렇게 되면 시간 초과가 난다. 

(p,q)를 q에 대해서 내림차순으로 정렬한다면, 다음과 같은 식이 나온다.

점화식에 sigma가 나온다?? -> 구간합배열을 활용해야겠다고 생각했다.

 

ll f(ll k) { //우유 k gallon 팔아서 나는 수익
	auto iter = lower_bound(pq.begin(), pq.end(), k);
	ll idx = iter - pq.begin(); 

	if (idx == 0) return k * store[idx].second;
	return ppq[idx-1] + (k - pq[idx-1]) * store[idx].second;
}

매개변수로는 i번째 소까지의 우유 산출량 합이다. 이것 역시 구간합배열 사용해서 상수시간에 넘겨줬다.

pq: sigma(q) , ppq: sigma(pq)이다.

 

 

다음은 코드 전문

#include <iostream>
#include <utility>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MAX = 1000001;

int n, m, r;
ll cow[1000001],rent[1000001];
ll pcow[1000001],pr[MAX];
vector<ll> pq, ppq;
P store[1000001];

ll f(ll k) { //우유 k gallon 팔아서 나는 수익
	auto iter = lower_bound(pq.begin(), pq.end(), k);
	ll idx = iter - pq.begin(); //k-1

	if (idx == 0) return k * store[idx].second;
	return ppq[idx-1] + (k - pq[idx-1]) * store[idx].second;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m >> r;
	pq.resize(m);
	ppq.resize(m);

	for (int i = 0; i < n; i++)	cin >> cow[i];
	for (int i = 0; i < m; i++) cin >> store[i].first >> store[i].second;
	for (int i = 0; i < r; i++) cin >> rent[i];

	sort(cow, cow + n, greater<ll>());
	sort(store, store + m, [](P p1, P p2) {
		return p1.second > p2.second; });
	sort(rent, rent + r, greater<ll>());

	pcow[0] = cow[0];
	for(int i=1; i<n; i++)
		pcow[i] = pcow[i - 1] + cow[i];

	pq[0] = store[0].first;
	for (int i = 1; i < m; i++)
		pq[i] = pq[i - 1] + store[i].first;

	ppq[0] = store[0].first * store[0].second;
	for (int i = 1; i < m; i++)
		ppq[i] = ppq[i - 1] + store[i].first * store[i].second;

	pr[0] = rent[0];
	for (int i = 1; i < r; i++)
		pr[i] = pr[i - 1] + rent[i];

	ll mx = pr[min(n,r)-1];
	for (int i = 0; i < n; i++) {
		ll suma = i<m ? f(pcow[i]) : f(pcow[m-1]);
		int j = n - 1 - i;
		ll sumb = j<r ? pr[j-1] : pr[r-1];
		mx = max(mx, suma + sumb);
	}

	cout << mx << '\n';
}

 

 

 

집에오는 길에 버스에서 풀어서 멀미가 너무 났다..

 

구간합배열을 만들어주는 코드를 제외하곤 코드가 깔끔한 것 같다.

 

공간을 너무 많이 써서 다른 분들보다 10배정도는 공간을 더 쓴것같다..ㅠㅠ