【题解】LA 3971【Assemble】

分析

这类最小值最大常用方法就是二分答案,假设答案为$x$,删除品质因子小于$x$的所有配件,如果可以组装出一台不超过$b$元的电脑,则标准答案$x \leq ans$,否则$ans < x$
判断可否组装符合预算,可以每一类配件选择最便宜的,如果超出,就不可能有解了。

代码

#include<cstdio>
#include<string>
#include<vector>
#include<map>
using std::map;using std::vector;using std::min;using std::max;using std::string;
int cnt;
map<string,int> id;
int ID(string s){
    if(!id.count(s)) id[s] = cnt++;
    return id[s];
}

const int MAXN = 1000 + 6;

class Component{
public:
    int price,quality;
};
int n,b;
vector<Component> comp[MAXN];

bool ok(int q){
    int sum = 0;
    for(int i = 0;i < cnt;i++){
        int cheapest = b + 1,m = comp[i].size();
        for(int j = 0;j < m;j++) if(comp[i][j].quality >= q) cheapest = min(cheapest,comp[i][j].price);
        if(cheapest == b + 1) return false;
        sum += cheapest;
        if(sum > b) return false;
    }
    return true;
}

int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d %d",&n,&b);
        cnt = 0;
        for(int i = 0;i < n;i++) comp[i].clear();
        id.clear();

        int maxq = 0;
        for(int i = 0;i < n;i++){
            char type[30],name[30];
            int p,q;
            scanf("%s %s %d %d",type,name,&p,&q);
            maxq = max(maxq,q);
            comp[ID(type)].push_back((Component){p,q});
        }
        int L = 0,R = maxq;
        while(L < R){
            int M = L + (R - L + 1) / 2;
            if(ok(M)) L = M;
            else R = M - 1;;
        }
        printf("%d\n",L);
    }

    return 0;
}