[BOJ 14247] 나무 자르기

문제 출처 : https://www.acmicpc.net/problem/14247

 

풀이 :

그리디(탐욕법) 문제입니다.

나무를 최대로 잘라가는 문제입니다.

따라서 나무가 자라는 길이가 최소인 애들이 제일 밸류가 떨어지므로

길이가 최소인 애들부터 잘라서 들고가면 됩니다.

 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> p;
 
int n;
p arr[100000];
priority_queue<p, vector<p>, greater<p>> q;
ll ret;
 
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i].second;
    for (int i = 0; i < n; i++) {
        cin >> arr[i].first;
        q.push(arr[i]);
    }
    for (int i = 0; !q.empty();i++) {
        p now = q.top();
        q.pop();
        ret += now.first * i + now.second;
    }
    cout << ret;
}