간단한 문제이다.
그리디 알고리즘을 쓰면 된다.
최대 무게가 작은 가방부터 보면서 담을 수 있는 보석 중에 가격이 젤 높은 보석을 담으면 된다.
가방 개수가 K개인데 가방마다 보석 N개를 전부 조사하면 O(NK)로 시간이 너무 오래 걸리니까
보석도 무게가 작은거부터 스택에 넣어두고 스택을 유지하면서 top을 담으면 된다.
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
int N,K;
long long bag[400005];
struct Data{
long long m,v;
bool operator<(const Data &r) const{
return m < r.m;
}
}jewel[400005];
priority_queue<long long> values;
int main()
{
scanf("%d %d",&N,&K);
for(int i=1;i<=N;i++)
{
scanf("%lld %lld",&jewel[i].m, &jewel[i].v);
}
for(int i=1;i<=K;i++)
{
scanf("%lld",&bag[i]);
}
sort(bag+1,bag+K+1);
sort(jewel+1,jewel+N+1);
int j=1;
long long ans=0;
for(int i=1;i<=K;i++)
{
while(jewel[j].m<=bag[i] && j<=N){
values.push(jewel[j].v);
j++;
}
if(!values.empty()){
ans+=values.top();
values.pop();
}
}
printf("%lld",ans);
}코드이다. 계속 런타임 에러가 생겨서 맞왜틀 고쳤는데 에러 발생 이유는 스택이 비었을 때 top과 pop 함수를 실행해서였다. 그래서 if(!values.empty())를 추가해서 고쳤다.
