0%

牛客网csp-s模拟赛 货物收集

晚上打牛客网,最近状态很差,1.5h打完第一题就滚粗了。
膜一下高二$AK$的大佬
题目链接https://ac.nowcoder.com/acm/contest/1102/A

看了下其他人的代码,感觉自己的还行?,所以来发下第一题的题解。
评测结果
因为是一颗树,不存在环,所以输入时候把终点处理一下,如果到起点的值比终点要大了,就直接更新到终点的值。看了半天才意识到是一棵树

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double LD;

const ll maxn=1e6+7;
ll n,W,all;
ll a[maxn],f[maxn],s[maxn];

template<class T> T read() {
    T x=0,w=1;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-') w=-w;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*w;
}
template<class T> inline T read(T&x) {
    return x=read<T>();
}
inline bool check(ll x) {
    ll sum=0;
    for(ll i=1;i<=n;i++) {
        if(f[i]<=x) sum+=a[i];
    }
    return sum>=W;
}

int main() {
    ll l=0,r=-2;
    read(n),read(W);
    for(ll i=2;i<=n;i++) {
        read(a[i]);
    }
    ll u,v,w;
    for(ll i=1;i<n;i++) {
        read(u),read(v),read(w);
        r=max(r,w);
        f[v]=w;
        if(f[u]>f[v]) f[v]=f[u];
    }
    while(l<=r) {
        ll mid=((l-r)/2)+r;
        if(!check(mid)) l=mid+1;
        else r=mid-1;
    }
    printf("%lld\n",l);
    return 0;
}