蓝书例题3971Assemble二分答案

组装电脑
题意 :
有b块钱,有很多种配件,每种配件至少选一件,每个配件有名字,参数(没用),价格,品质因子
现在如何买才能使得最小的品质因子最大(最大化最小值问题)

输入

1
18 800
processor 3500_MHz 66 5
processor 4200_MHz 103 7
processor 5000_MHz 156 9
processor 6000_MHz 219 12
memory 1_GB 35 3
memory 2_GB 88
6memory 4_GB 170 12
mainbord all_onboard 52 10
harddisk 250_GB 54 10
harddisk 500_FB 99 12
casing midi 36 10
monitor 17_inch 157 5
monitor 19_inch 175 7
monitor 20_inch 210 9
monitor 22_inch 293 12
mouse cordless_optical 18 12
mouse microsoft 30 9
keyboard office 4 10


输出

9


注意点

• 多组数据
• 考虑二分品质因子,$check$函数判断是否可以购买到价格小于b且最小品质大于等于mid的电脑

#define debug
#ifdef debug
#include
#include "/home/majiao/mb.h"
#endif#include
#include
#include
#include
#include
#include
#include
#include
#include #define MAXN (1024)
#define ll long long
#define int long long
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i&＃61;lef; i<&＃61;rig; i&＃43;&＃43;)
#define forj(lef, rig) for(int j&＃61;lef; j<&＃61;rig; j&＃43;&＃43;)
#define fork(lef, rig) for(int k&＃61;lef; k<&＃61;rig; k&＃43;&＃43;)
#define QAQ (0)using namespace std;#define show(x...) \do { \cout <<"\033[31;1m " <<#x <<" -> "; \err(x); \} while (0)void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << &＃39; &＃39;; err(x...); }namespace FastIO {char print_f[105];void read() { }void print() { putchar(&＃39;\n&＃39;); }template <typename T, typename... T2>inline void read(T &x, T2 &... oth) {x &＃61; 0;char ch &＃61; getchar();ll f &＃61; 1;while (!isdigit(ch)) {if (ch &＃61;&＃61; &＃39;-&＃39;) f *&＃61; -1; ch &＃61; getchar();}while (isdigit(ch)) {x &＃61; x * 10 &＃43; ch - 48;ch &＃61; getchar();}x *&＃61; f;read(oth...);}template <typename T, typename... T2>inline void print(T x, T2... oth) {ll p3&＃61;-1;if(x<0) putchar(&＃39;-&＃39;), x&＃61;-x;do{print_f[&＃43;&＃43;p3] &＃61; x%10 &＃43; 48;} while(x/&＃61;10);while(p3>&＃61;0) putchar(print_f[p3--]);putchar(&＃39; &＃39;);print(oth...);}
} // namespace FastIO
using FastIO::print;
using FastIO::read;int n, m, Q, K, tot;
map<string, int> mp;
vector<pair<int,int> > G[MAXN];void init() {tot &＃61; 0;mp.clear();for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;) G[i].clear();
}int ID(string s) {int& rx &＃61; mp[s];if(rx &＃61;&＃61; 0) rx &＃61; &＃43;&＃43; tot;return rx;
}/**二分品质因子,first为价格, second为品质因子,*/
int check(int mid) { // 返回最小品质因子大于等于mid的电脑要花多少钱int ret &＃61; 0;for(int i&＃61;1; i<&＃61;tot; i&＃43;&＃43;) {int tmin &＃61; INF; //品质因子能到达mid的最小价格//买品质因子大于等于mid的最便宜的配件for(int j&＃61;0; j<(int)(G[i].size()); j&＃43;&＃43;) if(G[i][j].second >&＃61; mid) {tmin &＃61; min(tmin, G[i][j].first);}if(tmin &＃61;&＃61; INF) return INF; //买不到这么高品质因子的配件 返回infret &＃43;&＃61; tmin;}return ret;
}signed main() {
#ifdef debugfreopen("test", "r", stdin);// freopen("out_main", "w", stdout);clock_t stime &＃61; clock();
#endifcin >> Q;while(Q--) {cin >> n >> m;string str, str2;init();int x, y;for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;) {cin >> str >> str2 >> x >> y; //x是价格, y是品质因子int pid &＃61; ID(str);G[pid].push_back({x, y});}int lef &＃61; 1, rig &＃61; 1e9&＃43;7, mid, ans &＃61; 0;while(lef < rig) {mid &＃61; (lef &＃43; rig) >> 1;int ret &＃61; check(mid);
// show(lef, rig, mid, ret);// 如果可以做出价格小于m且最小品质因子大于等于mid的电脑// 就记录答案,并尝试让答案大一点if(ret <&＃61; m) ans &＃61; mid, lef &＃61; mid &＃43; 1;else rig &＃61; mid;}printf("%lld\n", ans);}#ifdef debugclock_t etime &＃61; clock();printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif return 0;
}