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 6 memory 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
题意：你要组装一台电脑，现在给你不同种类的不同品质与价钱的部件，你的任务就是在不超过预算的前提下，从每一种部件中挑选一件，并且输出抽出的部件中最大的品质。
对于这种有最大最小值的题，没有思路时，一般用二分；
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
const int M = 1e3+5;
using namespace std;
struct node
{
char name[25], type[25];
int price, quality;
}s[M];
int n, b;
bool jud(int x){
int i, j, sum = 0, pos, Min;
for(i = 0; i < n;)
{
pos = -1; Min = 0x7fffffff;
for(j = i; j < n&&!strcmp(s[i].name, s[j].name); ++ j)
{
if(Min > s[j].price&&s[j].quality >= x)
{
Min = s[j].price; pos = j;
}
}
if(pos == -1)
return 0;
sum += Min;
i = j;
}
if(sum > b) return 0;
return 1;
}
int f(int left, int right)
{
while(left <= right)
{
int mid = (left+right)>>1;
if(jud(mid)) left = mid+1; //这里如果满足就让left = mid+1（因为是要求的最大值）
else right = mid-1;
}
return right;
}
int main()
{
int t;
scanf("%d", &t);
//printf("%d %d\n",Min, Max);
while(t --)
{
scanf("%d%d", &n, &b);
int Min = 0x7fffffff, Max = -0x7fffffff;
for(int i = 0; i < n; ++ i)
{
scanf("%s %s %d %d", s[i].name, s[i].type, &s[i].price, &s[i].quality); //这里的name与题意的type反了，不过不影响做题。。。
Min = min(Min, s[i].quality);
Max = max(Max, s[i].quality);
}
int ans = f(Min, Max);
printf("%d\n", ans);
}
return 0;
}
原文：http://blog.csdn.net/shengweisong/article/details/45276329