题意:
若干电脑配件,若干型号,每个型号都有价格和性能指数。求在K钱内的配置方案,使得最差性能最好。。
解法:
二分+判断
代码:
1
# include <cstdio>
2
# include <string>
3
# include <cstring>
4
# include <map>
5
# include <set>
6
# include <algorithm>
7
# include <vector>
8
using namespace std;
9
struct node
10

{
11
string name;
12
int p,q;
13
node(string na,int pr,int qu):name(na),p(pr),q(qu)
{};
14
};
15
struct cmp
16

{
17
bool operator()(const node &a,const node &b) const
18
{
19
return a.name<b.name;
20
}
21
};
22
int n,m;
23
map<string,vector<node> >data;
24
vector<int> refer;
25
bool chk(int mid)
26

{
27
long long total=0;
28
for(map<string,vector<node> >::iterator i=data.begin();i!=data.end();i++)
29
{
30
int tp=0xfffffff;
31
for(vector<node>::iterator j=(i->second).begin();j!=(i->second).end();j++)
32
if(j->q>=mid&&j->p<tp)
33
tp=j->p;
34
total+=tp;
35
}
36
return total<=(long long)m;
37
}
38
int main()
39

{
40
int test;
41
scanf("%d",&test);
42
while(test--)
43
{
44
scanf("%d%d",&n,&m);
45
data.clear();
46
refer.clear();
47
for(int i=0;i<n;i++)
48
{
49
char type[128],name[128];
50
int p,q;
51
scanf("%s%s%d%d",type,name,&p,&q);
52
data[string(type)].push_back(node(string(name),p,q));
53
refer.push_back(q);
54
}
55
sort(refer.begin(),refer.end());
56
vector<int>::iterator end=unique(refer.begin(),refer.end());
57
while(refer.end()!=end) refer.pop_back();
58
int s=0,e=refer.size()-1;
59
while(s<=e)
60
{
61
int mid=(s+e)>>1;
62
if(chk(refer[mid])) s=mid+1;
63
else e=mid-1;
64
}
65
printf("%d\n",refer[s-1]);
66
}
67
return 0;
68
}
69
70