生活随笔
收集整理的这篇文章主要介绍了
[UVALive 3971] Assemble
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
图片加载可能有点慢，请跳过题面先看题解，谢谢
又是道一眼题。。。
这道题最恶心的地方不是输入么。。。
直接二分一个 \(quality\) ，在每种配件里去找品质大于等于 \(quality\) 的价格最小的配件，将价格加起来，如果大于 \(b\)，则不合法
真是愉快的一天。。。
切了一天的水题。。。
$
$
//made by Hero_of_Someone
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<map>
#define inf (1<<30)
#define il inline
#define RG register
using namespace std;
il int gi(){ RG int x=0,q=1; RG char ch=getchar(); while( ( ch<'0' || ch>'9' ) && ch!='-' ) ch=getchar();if( ch=='-' ) q=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x; }int T,n,b,cnt,Max;
map<string,int>ma;
il int idx(string s){if(!ma.count(s)) ma[s]=++cnt;return ma[s];
}
struct com{int c,q;};
vector<com>vec[1010];il void init(){n=gi(),b=gi(),cnt=0,Max=0;for(RG int i=1;i<=n;i++) vec[i].clear();for(RG int i=1;i<=n;i++){RG char a[25],b[25]; scanf("%s%s",a,b);RG int c=gi(),q=gi(); Max=max(Max,q);vec[idx(a)].push_back((com){c,q});}
}il bool ck(int x){RG int sum=0;for(RG int i=1;i<=cnt;i++){RG int len=vec[i].size(),Min=inf;for(RG int j=0;j<len;j++)if(vec[i][j].q>=x) Min=min(Min,vec[i][j].c);sum+=Min; if(sum>b) return 0;}return 1;
}il void work(){RG int l=0,r=Max,ans=0;while(l<=r){RG int mid=(l+r)>>1;if(ck(mid)) ans=mid,l=mid+1;else r=mid-1;}printf("%d\n",ans);
}int main(){ T=gi(); while(T--){ init(); work(); } return 0; }
转载于:https://www.cnblogs.com/Hero-of-someone/p/7653037.html
总结
以上是生活随笔为你收集整理的[UVALive 3971] Assemble的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
