백준 2258번 정육점 C++

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

2258번: 정육점

 

어떤 고기를 샀을 때  그 가격보다 싼 고기는 무료로 얻을 수 있다.

고기의 가격은 오름차순, 가격이 같을때는 무게를 내림차순으로 정렬한다.

 

정렬된 순서로 고기의 무게를 더하다가 m보다 크거다 같게 되면 지금 고기의 가격과 같은 가격의 고기가 앞에 있는 만큼 더해서 가격을 측정하고, 측정한 값과 지금 고기보다 비싼 가격의 고기의 가격 중 싼 가격을 고른다. (지금보다 비싼 가격의 고기를 고른다면 전의 고기는 무료로 얻을 수 있기 때문)

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long; 

int n, m;

struct MeatInfo {
    int weight;
    int price;
    bool operator<(const MeatInfo& other) {
        if (price == other.price) return weight > other.weight;
        return price < other.price;
    }
};

vector<MeatInfo> v;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int weight, price;
        cin >> weight >> price;
        v.push_back({ weight,price });
    }
    sort(v.begin(), v.end());
    int index = 0;
    int lastPrice = 0;
    int sum = 0;
    int ans = -1;
    int sameCnt = 1;
    for (index = 0; index < n; index++) {
        sum += v[index].weight;
        if (lastPrice == v[index].price) {
            sameCnt++;
        }
        else {
            sameCnt = 1;
        }
        if (sum >= m) {
            ans = v[index].price * sameCnt;
            break;
        }
        lastPrice = v[index].price;
    }
    for (int i = index + 1; i < n; i++) {
        if (v[i].price > lastPrice) {
            ans = min(ans, v[i].price);
            break;
        }
    }
    cout << ans;
}