首页 > 代码库 > uva 12124 - Assemble
uva 12124 - Assemble
#include<cstdio> #include<cstring> #include<vector> #include<string> #include<map> #include<iostream> #include<algorithm> using namespace std; const int maxn = 1005; #define mem(a) memset(a,0,sizeof(a)) struct peijian{ int p; int q; }g[maxn][maxn]; map<string,int> ma; int tt[maxn]; int t=0; int n,b; bool cmp(peijian aa,peijian bb){ return aa.q<bb.q; } bool judge(int x) { int sum=0; for(int i=0;i<t;i++){ for(int j=0;j<tt[i];j++){ if(g[i][j].q>=x){ int m_temp=g[i][j].p; for(int k=j;k<tt[i];k++){ m_temp=min(g[i][k].p,m_temp); } sum+=m_temp; break; } } } if(sum<=b) return true; return false; } int main() { int T; scanf("%d",&T); while(T--){ t=0; mem(tt); scanf("%d%d",&n,&b); string type,name; int p,q,maxq=0; for(int i=0;i<n;i++){ cin>>type>>name>>p>>q; maxq=max(maxq,q); if(ma.count(type)){ int temp = ma[type]; g[temp][tt[temp]].p=p; g[temp][tt[temp]++].q=q; } else{ ma[type]=t++; int temp = ma[type]; g[temp][tt[temp]].p=p; g[temp][tt[temp]++].q=q; } } for(int i=0;i<t;i++){ sort(g[i],g[i]+tt[i],cmp); } for(int i=0;i<t;i++){ maxq=min(maxq,g[i][tt[i]-1].q); } int left=0,right=maxq,mid; while(left<right){ mid = left+(right-left+1)/2; if(judge(mid)){ left=mid; } else right = mid-1; } printf("%d\n",left); } return 0; }我是来保存代码的...
uva 12124 - Assemble
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。