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

 

21761번: 초직사각형

1차원 공간에서의 선분, 2차원 공간에서의 직사각형, 3차원 공간에서의 직육면체를 생각해 보자. 선분의 크기는 변수 $A$로, 직사각형의 크기는 두 개의 변수 $A$와 $B$로, 직육면체의 크기는 세 개

www.acmicpc.net

 

 

[난이도] Gold1
[유형] Greedy

[풀이]
나중에..

 

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int N,K;
ll v[4];
priority_queue<int> pq[4];
struct P{
    int idx,l;
};
bool cmp(P& a,P& b){
    return (a.l+v[a.idx])*v[b.idx] > (b.l+v[b.idx])*v[a.idx];
}
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<4;i++) scanf("%d",&v[i]);
    while(N--){
        char c;
        int l;
        scanf(" %c %d",&c,&l);
        pq[c-'A'].push(l);
    }
    while(K--){
        vector<P> t;
        for(int i=0;i<4;i++){
            if(pq[i].empty()) continue;
            t.push_back({i,pq[i].top()});
        }
        sort(t.begin(),t.end(),cmp);
        auto [idx,l] = t[0];
        pq[idx].pop();
        v[idx]+=l;
        printf("%c %d\n",idx+'A',l);
    }
}


https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold1/초직사각형.cpp

+ Recent posts