| MM买电脑 | ||||||
| ||||||
| Description | ||||||
|
在学习了一些理论基础后，MM决定要买一台电脑，搞ACM没有电脑是不行的，可是MM对电脑硬件方面一窍不通，于是找来GG帮忙，GG可是软硬件通吃，装一台电脑更是不在话下了。为了适应需求，他们打算购买电脑的各零件，然后回来自己组装。对于电脑中的每一个零件他们买且只买一个。现在的问题是每一种零件都有好多品牌，品牌下又分好多型号，不同型号的价钱不等，同时它们的质量也不一样。而整个电脑的质量取决于各零件中质量最差的那个。所以我们需要在不超出预支金额的情况下，尽量使得质量最差的那个零件的质量最大化，这样我们购买的电脑总体质量才不至于太低。 | ||||||
| Input | ||||||
|
输入数据的第一行有一个整数T，代表测试数据的组数。接下来有T组测试数据。 对于每组测试数据： 第一行有两个整数n和b，分别代表需要购买的零件种类，以及预支金额。 第二行到第n+1行每行代表一个零件的一些信息，这些信息以”类型 型号 价格 质量”的格式给出，它们两两之间用空格分开。这四个属性中： “类型”为一个字符串，仅包含小写字母。不超过20个字符。 “型号”为一个字符串，包含字母，数字，下划线。不超过20个字符。 “价格”为一个正整数。 “质量”为一个正整数，数值越大则质量越高。 范围： T ≤ 100 1 ≤ n ≤ 1 000 1 ≤ b ≤ 1 000 000 000 0 ≤ price ≤ 1 000 000 0 ≤ quality ≤ 1 000 000 000 | ||||||
| Output | ||||||
|
对于每组测试数据，输出一个整数并换行。这个整数代表新电脑的最大质量（即最小的质量最大是多少） | ||||||
| Sample Input | ||||||
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 | ||||||
| Sample Output | ||||||
| 9 | ||||||
| Hint | ||||||
| 每组数据保证有解。 | ||||||
| Source | ||||||
| 2012 Spring Contest 5 - Binary Search, Greedy, DP |
分析：
刚开始我对性能从大到小进行枚举，对于每一类物品取价格大于等于该枚举值的价格最小的物品
900+过的
其实对于所有的性能进行二分即可
if(cost > per_cost)
high = mid;
else
low = mid;
这样就可以了
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <map> 6 using namespace std; 7 8 const int maxn = 1005; 9 10 struct point 11 { 12 string s; 13 int a, b; 14 }poin[maxn]; 15 16 int n, sum_b; 17 bool check(int x) 18 { 19 int sum = 0; 20 string s1 = poin[0].s; 21 int st = 0, en = 0; 22 for(int i = 0; i < n; i++) 23 { 24 if(poin[i].s != s1) 25 { 26 en = i - 1; 27 bool flag = false; 28 int max_num = 0xffffff; 29 for(int i = st; i <= en; i++) 30 { 31 if(poin[i].b >= x) 32 { 33 flag = true; 34 if(max_num > poin[i].a) 35 { 36 max_num = poin[i].a; 37 } 38 } 39 } 40 if(!flag) 41 return false; 42 sum += max_num; 43 st = i; 44 s1 = poin[i].s; 45 } 46 } 47 //printf("*%d\n",sum); 48 if(sum <= sum_b) 49 return true; 50 else 51 return false; 52 } 53 54 int main() 55 { 56 int t; 57 //freopen("1511.txt","r",stdin); 58 scanf("%d",&t); 59 while(t--){ 60 scanf("%d %d",&n, &sum_b); 61 string str; 62 int num[maxn] = { 0 }; 63 int k = 0; 64 for(int i = 0; i < n; i++) 65 { 66 cin>>poin[i].s>>str>>poin[i].a>>poin[i].b; 67 num[k++] = poin[i].b; 68 } 69 poin[n].s = "asdf"; 70 n++; 71 sort(num, num + k); 72 //int ans_num[maxn]; 73 //int k_num = 1; 74 //ans_num[0] = num[0]; 75 //for(int i = 1; i < k; i++){ 76 // if(num[i] != num[i - 1]){ 77 //ans_num[k_num++] = num[i]; 78 //printf("%d ",ans_num[k_num - 1]); 79 //} 80 //} 81 int low = 0, high = k - 1; 82 while(low <= high){ 83 //printf("%d\n",low); 84 int mid = (low + high) >> 1; 85 if(!check(num[mid])) 86 high = mid - 1; 87 else 88 low = mid + 1; 89 } 90 //printf("%d %d\n",high, low); 91 /* 92 //num[k] = 0; 93 int ans = 0; 94 for(int i = k - 1; i >= 0; i--) 95 { 96 97 if(num[i] == num[i+1]) 98 continue; 99 if(check(num[i])) 100 { 101 ans = num[i]; 102 break; 103 } 104 // printf("%d %d\n",num[i],check(num[i])); 105 } 106 */ 107 printf("%d\n",num[high]); 108 } 109 return 0; 110 }
hlg-1332 买电脑 ---二分,布布扣,bubuko.com
原文：http://www.cnblogs.com/zhanzhao/p/3734083.html
