LA3971组装电脑

题意：

你有b块钱，想要组装一台电脑，给你提供一些零件，每种零件提供一个或几个，组装电脑的前提是每种零件只能也必须选择一个，每种零件都有自己的种类，名字，价格，还有品质，要求是在能配成电脑的前提下所有零件中最小的品质最大（品质越大越好）。

思路：

最小的最大，第一反应就是二分，这个题目也不例外，我们只要二分品质就行了，品质的数据感觉比较大，但是直接去枚举应该也能过，如果担心过不了可以先把零件中所有涉及的品质都拿出来，答案肯定是这些数据中的一个，我们只要sort下，然后去二分枚举sort后的品质数组，每次枚举我们都会得到一个当前的品质值，对于每种物品，我们肯定是选择品质值满足要求的最小花费的那个零件，其他的没什么，细心点就行了，具体细节可以看代码。



#include<map>

#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<string>

#define N 1000 + 10

using namespace std;

typedef struct

{

int jg ,pz;

char str[22];

}NODE;

NODE node[N];

map<string ,int>mark;

int tmp[N] ,P[N] ,nowidp;

bool camp(NODE a, NODE b)

{

return a.jg < b.jg;

}

bool ok(int nowpz ,int n ,int szl ,int b)

{

mark.clear();

int sszl = 0 ,nowb = 0;

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

{

if(node[i].pz < nowpz) continue;

if(!mark[node[i].str]) sszl ++ ,nowb += node[i].jg;

mark[node[i].str] = 1;

}

return sszl == szl && nowb <= b;

}



int main ()

{

int n ,b ,i ,szl ,t;

char str[22];

scanf("%d" ,&t);

while(t--)

{

scanf("%d %d" ,&n ,&b);

mark.clear();

szl = 0;

for(i = 1 ;i <= n ;i ++)

{

scanf("%s %s %d %d" ,node[i].str ,str ,&node[i].jg ,&node[i].pz);

if(!mark[node[i].str]) szl ++;

mark[node[i].str] = 1;

tmp[i] = node[i].pz;

}

sort(node + 1 ,node + n + 1 ,camp);

sort(tmp + 1 ,tmp + n + 1);

nowidp = 0;

for(i = 1 ;i <= n ;i ++)

if(i == 1 || tmp[i] != tmp[i-1])

P[++nowidp] = tmp[i];



int low = 1 ,up = nowidp ,mid ,Ans = P[1];

while(low <= up)

{

mid = (low + up) / 2;

if(ok(P[mid] ,n ,szl ,b))

{

Ans = P[mid];

low = mid + 1;

}

else up = mid - 1;

}

printf("%d\n" ,Ans);

}

return 0;

}

巴特西

LA3971组装电脑

最新文章

热门文章