백준 23559 밥 C++

요약

밥을 잘먹으면 되는이야기

 

 N일간의 최대치를 구해야하는데, 5000원 1000원이 있다.

 

1. 먼저 1000원으로 N일치를 채우고, 가진 돈에서 1000원 * N을 제한다.

2. 5000원과 1000원의 차를 큐에 넣는다.

3. 차가 제일 큰 수부터 가능한 예산에서 뽑는다.

 

A_0, A_1, ... A_N을 뽑고, 그 다음에 ( B_k - A_k )를 뽑기에 최대값을 뽑을 수 있다.

 

답

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define ll long long
using namespace std;
int main(){
  int n,x;
  cin>>n>>x;
  vector<pair<ll,ll>> v(n,pair<ll,ll>());
  for(int i=0;i<n;++i){
    cin>>v[i].first>>v[i].second;
  }
  vector<bool> visited(n,false);
  ll ans=0;
  priority_queue<ll> q;
  for(int i=0;i<n;++i){
    ans+=v[i].second;
    x-=1000;
    q.push(v[i].first-v[i].second);
  }
  while(!q.empty()&&x>=4000){
    ll val=q.top();
    q.pop();
    if(val<=0) break;
    x-=4000;
    ans+=val;
  }
  cout<<ans;
}