핵심 아이디어

<aside> 💡

컴퓨터 성능 $k$에 대해 이분탐색

</aside>

각 부품에서 $q$가 $k$이상인 부품 중 $p$값이 가장 낮은 부품을 찾고 그러한 부품들의 $p$합이 $c$를 넘는지 넘지 않는지를 확인하면 된다.

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

struct Node
{
    int p, q;
    bool operator<(Node o){
        if(q == o.q) return p<o.p;
        return q< o.q;
    }
};

int n, b;
map<string, int> tidx;

void solve()
{
    int m = 0;
    tidx.clear();
    vector<Node> parts[1'001];
    
    cin >> n >> b;
    for(int i = 0; i<n; i++){
        string ty, name;
        int p, q;
        cin >> ty >> name >> p >> q;
        
        if(tidx.count(ty)){
            parts[tidx[ty]].push_back({p,q});
        }
        else{
            tidx[ty] = m;
            parts[m++].push_back({p,q});
        }
    }
    
    for(int i = 0; i<m; i++){
        sort(parts[i].begin(), parts[i].end());
    }
    
    ll lo = 0, hi = 1e+9+1;
    while(lo+1<hi){
        ll mid = lo+hi>>1;
    
        bool flag = true;
        ll cost = 0;
        for(int i = 0; i<m; i++){
            int curCost = 1e+9+1;
            for(auto[p, q]: parts[i]){
                if(q<mid) continue;
                curCost = min(curCost, p);
            }

            cost += curCost;
            if(cost>b){
                flag = false;
                break;
            }
        }
    
        if(flag) lo = mid;
        else hi = mid;
    }
    
    cout << lo <<"\\n";
}

signed main()
{
    FASTIO;
    int tc; cin >> tc;
    while(tc--) solve();
    return 0;
}