EOJ Monthly 2019.2 (based on February Selection) E. 中位数

题目链接:https://acm.ecnu.edu.cn/contest/140/problem/E/

题意:略

思路:考虑二分答案,我们需要验证路径最大的中位数是否≥mid。我们把所有的点权做−1/1变换,即≥mid的点权变为1否则变为−1。根据题面路径中位数的定义,我们可以发现,如果这条路径的中位数≥mid那么做了−1/1变换以后,这条路径上的点权和≥0。而我们现在需要知道的问题是路径最大的中位数是否≥mid ,也就是说,最大的路径点权是否≥0 。跑一遍最长路就好了。

#include <bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e6+10;
int n,m,i,x,y,a[N],b[N],d[N];
bool vis[N];
vector<int>G[N];
void dfs(int u){
    if (vis[u]) return;
    vis[u]=1;
    if (u==n){
        d[n]=b[n];
        return;
    }
    for (int i=0;i<(int)G[u].size();++i){
        int v=G[u][i];
        dfs(v);
        d[u]=max(d[u],d[v]);
    }
    if (d[u]!=-1e7) d[u]+=b[u];
}
bool check(int x){
    for (i=1;i<=n;++i) b[i]=a[i]>=x?1:-1,d[i]=-1e7,vis[i]=0;
    dfs(1);
    return d[1]>=0;
}
int main(){
    read(n),read(m);
    for (i=1;i<=n;++i) read(a[i]);
    for (i=1;i<=m;++i){
        read(x),read(y);
        G[x].PB(y);
    }
    int l=0,r=1e9,ans=-1;
    while (l<=r){
        int mid=l+((r-l)>>1);
        if (check(mid)){
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注