首页 > 代码库 > UVa 12124 - Assemble
UVa 12124 - Assemble
题目:你要去自己买个组装机,现在给你每个零件的类别、名字、价钱、级别,以及你有的钱数,
求能组装成的机器的最大级别(机器的所有零件中的最小级别,即最小值最大)。
分析:分治、dp。看起来很像是dp,不过本题可以利用二分求解(我这里二分套二分了)。
首先,将所有的零件按照级别递减排序,此时装机的总代价递减(比原来多了新的参考零件);
然后,二分级别,每次找到不低于当前级别的所有零件(排序后,一定连续,可以二分求解);
计算这些零件能够构成计算机的最小代价,不能组成就返回max;
最后,求出的结果,即为可以得到的最大的级别。
说明:题意略坑,要求每种市面上有的零件都要买一件,RE好多次╮(╯▽╰)╭。
#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> using namespace std; typedef struct cnode { char type[21]; char name[21]; int price; int level; }component; component C[1004]; char list[1004][21]; int gettype( char* type, int n ) { for ( int i = 0 ; i < n ; ++ i ) if ( !strcmp( list[i], type ) ) return i; strcpy(list[n], type); return n+1; } bool cmp( component a, component b ) { return a.level > b.level; } int temp[1004]; int test( int n, int s ) { int mark = 0,sum = 0,t; for ( int i = 0 ; i < s ; ++ i ) temp[i] = 1000001; for ( int i = 0 ; i < n ; ++ i ) { t = gettype( C[i].type, s ); if ( temp[t] > C[i].price ) temp[t] = C[i].price; } for ( int i = 0 ; i < s ; ++ i ) if ( temp[i] == 1000001 ) return 1000000001; else sum += temp[i]; return sum; } int bs( int r, int key ) { int l = 0,mid; while ( l < r ) { mid = (r+l)/2; if ( C[mid].level >= key ) l = mid+1; else r = mid; } return r; } int main() { int n,m,p; while ( ~scanf("%d",&n) ) while ( n -- ) { scanf("%d%d",&m,&p); int list_size = 0; for ( int i = 0 ; i < m ; ++ i ) { scanf("%s%s%d%d",&C[i].type,&C[i].name,&C[i].price,&C[i].level); list_size = max(list_size, gettype( C[i].type, list_size )); } sort( C, C+m, cmp ); int mid,l = 0,r = m-1; while ( l < r ) { mid = (l+r)/2; if ( test(bs(m-1,C[mid].level),list_size) > p ) l = mid+1; else r = mid; } printf("%d\n",C[r].level); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。