首页 > 代码库 > 【HDOJ】2333 Assemble
【HDOJ】2333 Assemble
二分+贪心策略。其中注释处很重要。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 using namespace std; 7 8 #define MAXL 25 9 #define MAXN 100510 #define INF 100000000011 12 typedef struct {13 char name[MAXL];14 int p, q;15 } comp_st;16 17 comp_st comps[MAXN];18 int t, n, b;19 int ns[MAXN], nn;20 21 bool comp(comp_st a, comp_st b) {22 int tmp = strcmp(a.name, b.name);23 if (tmp == 0)24 return a.q > b.q;25 else26 return tmp < 0;27 }28 29 bool chk(int x) {30 int i, j;31 int sum = 0, min;32 33 for (i=0; i<nn; ++i) {34 min = INF;35 for (j=ns[i]; j<ns[i+1]; ++j) {36 if (comps[j].q>=x && min>comps[j].p)37 min = comps[j].p;38 }39 /* pay attention to here.*/40 if (min == INF)41 return false;42 sum += min;43 }44 return sum<=b;45 }46 47 int main() {48 int i, min, max, mid, v;49 char str[MAXL];50 51 scanf("%d", &t);52 53 while (t--) {54 scanf("%d %d", &n, &b);55 min = INF;56 max = 0;57 for (i=0; i<n; ++i) {58 scanf("%s %s %d %d", comps[i].name, str, &comps[i].p, &comps[i].q);59 if (comps[i].q < min) min = comps[i].q;60 if (comps[i].q > max) max = comps[i].q;61 }62 sort(comps, comps+n, comp);63 ns[0] = 0;64 for (nn=0,i=1; i<n; ++i) {65 if (strcmp(comps[i-1].name, comps[i].name) != 0)66 ns[++nn] = i;67 }68 ns[++nn] = n;69 v = 0;70 while (min <= max) {71 mid = (min+max)/2;72 if ( chk(mid) ) {73 v = mid;74 min = mid+1;75 } else {76 max = mid-1;77 }78 }79 printf("%d\n", v);80 }81 82 return 0;83 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。