这道题目非常的不错！就是你看着非常有思路也想作对的，但是其中就是给你设置了很多的陷阱让你做不出来，这道题目对于算法知识很扎实的人来看，应该是一道水题，但是对于我这种算法知识一点都不扎实的人来说，这题做出来就出奇了！
这题是一个综合的题型，考察到的知识点分别有：
其一、vector的运用，一个vector量是一个链表型的数组，但是如果开多一点，一个vector的数组，那可就是一个邻接表了，这对于建立那些数据量非常大的数据模型来说，可谓是非常的方便。
其二、map的应用，其实呢，你把所有的种类都存到一个数组里面，每次都遍历看看有没有存该数据也是可以的。但是那是没学过数据结构的人做的。map就是一种对应关系的hash，而且是一个非常方便的hash，一个量对应这一个量，这是多么的方便呀。而且其中的key还可以是string，或者是类的对象，这是多么的方便啊。
其三、关于求“满足题意的最小值最大的问题”，即求这其中拉低档次的质量因子要最大，就是说，在满足题意的要求一堆数字中最小值要尽量大。这种问题要用到的是二分答案。（我怎么不知道……）。
这些都具备了，你也不一定能够快速的完成程序的编写，因为这里包含的知识点，需要注意的点太多了，一步小心就可能挂了，刚开始的时候以为硬件一共就那8种，因为组装电脑你不可能缺个什么硬件吧，题中给的样例是能通过的，所以就私自认为就有这么几种硬件了。所以一直在错。
其实，最重要的，我最想提醒我自己注意的那段还是二分答案，这是一个很棒的思路，因为折半查找，比你普通枚举要快很多，为log（n），而其实像我上次写二分的时候，其中有个教授说的那样，90%的程序员二分是写不全对的。主要的问题到底在哪，主要的问题就是想当然，不自己去推理，条件没有弄明白。mid 求的并不能使程序迅速的返回正确的值。这些经验是考平时多编程积累起来的。而且还要自己多懂脑筋，不要想当然。
现在自己讨论一下mid的求解 int mid = left + (right - left) / 2;这种求法使得解向左逼近，也就是满足的时候应该是右满足，而左不满足的时候左加1，即左开右闭（当然如果是找精确的数字的话，那当然可以直接左开右开，加一个判断条件就可以了）。还有一种 int mid = left + (right - left + 1) / 2，这种当然就是向右逼近的，所以应该是左臂右开，即找到一个答案如果满足了， 那么就给了左方，最后求的最大值就是左边的值（上面左开右闭的就是求最小值的）。
这得在实践中，多次运用，多次时间才有可能运用自如。
不说了，贴出代码：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <map>
#include <string>
using namespace std;
int N, buget;
struct Component
{
int price;
int quality;
};
vector <Component> com[1011];
map <string, int> mp;
int cnt_map;
int min(int a, int b)
{
return a < b ? a : b;
}
int converse(char *s)
{
if (!mp.count(s))
{
mp[s] = cnt_map++;//给map hash功能的同时将总共的种类数也求出来
}
return mp[s];
}
void init()
{
cnt_map = 0;
for (int i = 0; i < N; i++)
{
com[i].clear();
}
mp.clear();
}
bool check(int q)
{
int sum = 0;
for (int i = 0; i < cnt_map; i++)
{
int cheap = buget + 1;
int m = com[i].size();
for (int j = 0; j < m; j++)
{
if (com[i][j].quality >= q)
{
cheap = min(cheap, com[i][j].price);
}
}
if (cheap == buget + 1) //如果所有的价钱都比自己拥有的价钱高,那直接返回false
{
return false;
}
sum += cheap;
if (sum > buget) //只要出现了总钱数不能购买所有的硬件就返回false
{
return false;
}
}
return true;
}
int main()
{
int T;
char compo[22];
char com_name[22];
int price;
int q;
scanf("%d", &T);
while (T--)
{
init(); //这个很重要,每次都要清空map,vector里面的值
scanf("%d%d", &N, &buget);
int maxq = -1;
for (int i = 0; i < N; i++)
{
scanf("%s%s%d%d", compo, com_name, &price, &q);
int id = converse(compo);
com[id].push_back((Component){price, q});
if (maxq < q)
{
maxq = q; //求出所有中的quality最大值
}
}
int left = 0;
int right = maxq;
while (left < right)
{
int mid = left + (right - left + 1) / 2; //这是整个程序的精髓,如果这个没有研究透,题目你也是做不出来的.
if (check(mid))
{
left = mid;
}
else
{
right = mid - 1;
}
}
printf("%d\n", left);
}
// system("pause");
return 0;
}