LA3971 组装电脑

思路：二分，就是在不超过b的预算下，使得品质的最小值最大化。关键还是判断函数吧。

　　　假设答案为x，判断函数，就是每一个种类的配件的品质最基本的品质要大于x，然后找出最小的值。这样的配件品质之和的价格要小于b元。

　　　则表明x是答案之一。但是，不一定是最优答案。最后答案就要看二分的方向了。

#include<iostream>

#include<string>

#include<map>

#include<vector>

#include<algorithm>

#include<string>

using namespace std;

const int maxn = 1e3 + ;

int cnt;

map<string, int>ss;

int id(string x){

    if (!ss.count(x))ss[x] = cnt++;

    return ss[x];

}

struct node{ int x, y; };

vector<node>comp[maxn];

int t, n, b;

//品质不小于x的组件能否组装为不超过b的电脑

bool ok(int x){

    int sum = ;

    for (int i = ; i < cnt; ++i){

        int pest = b + , m = comp[i].size();

        for (int j = ; j < m;++j)        //找大于x的最小值

        if (comp[i][j].y >= x)pest = min(pest, comp[i][j].x);

        if (pest == b + )return ;

        sum += pest;

        if (sum>b)return ;

    }

    return ;

}

int main(){

    cin >> t;

    while (t--){

        cin >> n >> b;

        //初始化

        cnt = ;

        for (int i = ; i < n; ++i)comp[i].clear();

        ss.clear();            int maxq = ;

        for (int i = ; i < n; ++i){

            //初始化

            string type, name;    int x, y;

            cin >> type >> name >> x >> y;    maxq = max(maxq, y);

            comp[id(type)].push_back(node{ x, y });

        }

        int L = , R = maxq;

        while (L < R){

        //    cout << "L=" << L << "  R=" << R << endl;

            int M = L + (R - L + ) / ;

            if (ok(M))L = M;    else R = M - ;

        }

        cout << L << endl;

    }

    return ;

}