LA 3971 组装电脑

题目：

传送门

题解：

大意是给一些零件（属性：种类，名称（没用），加格，品质），电脑的品质取决于最低的配件品质，问有的钱能买的最高的电脑品质。

---

这个题一看就是二分，O(n^2 * logn * T)的算法也很好想，就是排序之后二分下标，贪心可check。字符串的话，我使用的是类似离散的方法编号而避免了用map，因为map+string会很慢（但是string还是很慢），虽然实际上复杂度远小于上界，但是n=1000时O(n^2 * logn * T)=10^9，感觉复杂度太高了。我想到一种解法是O(n * (logn)^2 * T)可是老是写不对，因为我就是个大蒟蒻。我想的是先对品质也离散化，将品质作为权值，插入到权值线段树中（这样会建n棵树，不过总时间复杂度仍然是O(nlogn)），然后这个位置放它的cost，二分的时候直接在权值线段树上query，log的时间就能得到最小的cost了。 再回顾一下， T组数据 T |——(类型离散 )nlogn + (品质离散) nlogn +(建树一共) nlogn |——(二分，注意去二分下标而不是二分答案，二分答案是log1e9的) logn |———–(枚举类型，对于每个类型query一次) nlogn 这样差不多就是O(T * n * (logn) ^ 2 )的了，但是由于本人太弱未能将其实现，若有实现者请一定告诉我（这种方法跑的快不快qwq）。

代码：

这里是O( n^2 * logn * T)的算法。 //QWsin #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=1000+10; const int INF=(1<<30); struct Node{ int kind,cost,qua;Node(){} Node(int k,int c,int q):kind(k),cost(c),qua(q){} }a[maxn]; vector<Node>v[maxn]; int n,V,qua[maxn]; string tmp[maxn],s[maxn]; inline int read() { int ret=0;char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0'; return ret; } inline int check(int ans,int k) { int sum=0; for(int i=1;i<=k;i++) { int Min=INF,sz=v[i].size(); for(int j=0;j<sz;j++) if(v[i][j].qua>=ans) Min=min(Min,v[i][j].cost); if(Min==INF||(sum+=Min)>V) return 0; } return 1; } void solve() { cin>>n>>V; for(int i=1;i<=n;i++) v[i].clear(); for(int i=1;i<=n;i++) { cin>>s[i];tmp[i]=s[i]; scanf("%*s");a[i].cost=read(); qua[i]=a[i].qua=read(); } sort(tmp+1,tmp+n+1); int k=unique(tmp+1,tmp+n+1)-tmp-1; for(int i=1;i<=n;i++) a[i].kind=lower_bound(tmp+1,tmp+k+1,s[i])-tmp; for(int i=1;i<=n;i++) v[a[i].kind].push_back(a[i]); sort(qua+1,qua+n+1); int l=1,r=n,ans; while(l<=r) { int mid=((l+r)>>1); if(check(qua[mid],k)) ans=qua[mid],l=mid+1; else r=mid-1; } printf("%d\n",ans); } int main() { int T;cin>>T; while(T--)solve(); return 0; }