为什么D题只有百分之四十的通过率
#include<bits/stdc++.h> using namespace std; using ll=long long; const int N=1e5+10; int n,m,p[N],s[N]; ll c; struct Edge{ int a,b,w; bool operator< (const Edge &W) const{ return w<W.w; } }edge[N]; int find(int u) { if(p[u]!=u) p[u]=find(p[u]); return p[u]; } vector<int> a; ll check(int u) { ll ans=0; int i=upper_bound(a.begin(), a.end(), u) - a.begin(); int lenth=a.size(); for(int j=lenth,k=i;j>=i&&k<lenth;j--,k++) { ans+=a[k]*(j-i); } return ans; } int main() { cin>>n>>m>>c; int j=0; for(int i=0;i<m;i++) { cin>>edge[i].a>>edge[i].b>>edge[i].w; } sort(edge,edge+m); for(int i=1;i<=n;i++) p[i]=i; for(int i=0;i<m;i++) { int x=edge[i].a,y=edge[i].b; if(find(x)!=find(y)) { p[find(x)]=find(y); a.push_back(edge[i].w); if(edge[i].w>j) j=edge[i].w; } } int l=0; int r=j; while(l<r) { int mid=(l+r)/2; if(check(mid)<=c) r=mid; else l=mid+1; } cout<<l; }
}
全部评论
(1) 回帖