[NOIP2018]赛道修建（二分+multiset）

考场上打了一个 \(vector\) 解法，因为我当时不会 \(multiset\)

好吧，我来讲一讲今年的 \(tgD1T3\)

首先，这题 \(55\) 分是不难想的

1、 \(b_i=a_i+1\) 的情况（一条链）

解法：把所有边权记录下来，这种情况等价于将序列分割成 \(m\) 段，使 \(m\) 段区间和的最小值最大

那么二分 \(m\) 段区间和的最小值，然后 \(O(n)\) 贪心扫一遍，时间复杂度 \(O(nlogn)\)

namespace subtask1{

    int a[maxn];

    void dfs(int x,int fa){

        for(int i=head[x],y;i;i=e[i].next){

            y=e[i].to;

            if(y==fa) continue;

            dfs(y,x);

            a[x]=e[i].val;

        }

    }

    int check(int k){

        int t=0,now=0;

        for(int i=1;i<n;i++){

            if(now+a[i]>=k){

                now=0;

                t++;

            }

            else now+=a[i];

        }

        return t>=m;

    }

    void solve(){

        dfs(1,0);

        int l=1,r=sum,mid;

        while(l<r){

            mid=l+r+1>>1;

            if(check(mid)) l=mid;

            else r=mid-1;

        }

        printf("%d\n",l);

        return ;

    }

}

2、 \(m=1\) 的情况（树的直径）

解法：取一条最长链，即为树的直径问题，记录一下最大值和次大值，每次把最大

值传到它的父亲，时间复杂度 \(O(n)\)

namespace subtask2{

    int dfs(int x,int fa){

        int sum1=0,sum2=0;

        for(int i=head[x],y;i;i=e[i].next){

            y=e[i].to;

            if(y==fa) continue;

            sum2=max(sum2,dfs(y,x)+e[i].val);

            if(sum2>sum1) swap(sum1,sum2);

        }

        ans=max(ans,sum1+sum2);

        return sum1;

    }

    void solve(){

        dfs(1,0);

        printf("%d\n",ans);

        return ;

    }

}

3、\(a_i=1\)的情况（菊花图）

解法：把所有边权记录下来，从大到小排序。设边权为 \(w\)，答案即为 \(w_1+w_{2m-1},w_2+w_{2m-2},...,w_m+w_{m+1}\) 的最小值，时间复杂度 \(O(nlogn)\)

namespace subtask3{

	int a[maxn];

	bool cmp(int a,int b){

		return a>b;

	}

	void solve(){

		for(int i=head[1],y;i;i=e[i].next){

			y=e[i].to;

			a[y-1]=e[i].val;

		}

		sort(a+1,a+n,cmp);

		int ans=inf;

		for(int i=1;i<=m;i++)

			ans=min(ans,a[i]+a[2*m-i+1]);

		printf("%d\n",ans);

	}

}

分支不超过 \(3\) 的话其实就是正解的弱化版

看到题意描述第一反应就是先二分那个修建的\(m\)条赛道中长度最小的赛道的长度 \(k\) ，然后 \(O(n)\) 或 \(O(nlogn)\) 判断

那么怎么判断呢？

对于每个结点，把所有传上来的值 \(val\) 放进一个 \(multiset\) ，其实这些值对答案有贡献就两种情况：

\(val\geq k\)
\(val_a+val_b\geq k\)

那么第一种情况可以不用放进 \(multiset\)，直接答案 \(+1\) 就好了。第二种情况就可以对于每一个最小的元素，在 \(multiset\) 中找到第一个 \(\geq k\)的数，将两个数同时删去，最后把剩下最大的值传到那个结点的父亲

我出考场后想为什么这种解法是正确的，有没有可能对于有些情况直接传最大的数会使答案更大？

当然不会。这个数即使很大也只能对答案贡献加 \(1\)，在其没传上去的时候可以跟原来结点的值配对，也只能对答案贡献加 \(1\)

\(multiset\) 版：

int dfs(int x,int fa,int k){

    s[x].clear();

    int val;

    for(int i=head[x],y;i;i=e[i].next){

        y=e[i].to;

        if(y==fa) continue;

        val=dfs(y,x,k)+e[i].val;

        if(val>=k) ans++;

        //直接处理第一种情况

        else {

            s[x].insert(val);

        }

    }

    int Max=0;

    while(!s[x].empty()){

        if(s[x].size()==1){

            return max(Max,*s[x].begin());

        }

        //把最大的给传上去

        it=s[x].lower_bound(k-*s[x].begin());

        //二分到那个值

        if(it==s[x].begin()&&s[x].count(*it)==1) it++;

        //若找到的就是它自己且当前值的count==1,迭代器++

        if(it==s[x].end()){

            Max=max(Max,*s[x].begin());

            s[x].erase(s[x].find(*s[x].begin()));

        }

        //若没有找到比k-*s[x].begin()大的，就取个最大值，把*s[x].begin()删掉

        else {

            ans++;

            s[x].erase(s[x].find(*it));

			s[x].erase(s[x].find(*s[x].begin()));

        }

        //处理第二种情况

    }

    return Max;

    //把最大值传上去

}

\(vector\) 版：

while(!s[x].empty()){

    if(s[x].size()==1){

        return max(Max,*s[x].begin());

    }

    it=lower_bound(s[x].begin(),s[x].end(),k-*s[x].begin());

    if(it==s[x].begin()) it++;

    if(it==s[x].end()){

        Max=max(Max,*s[x].begin());

        s[x].erase(s[x].begin());

    }

    else {

        ans++;

        s[x].erase(it);

        s[x].erase(s[x].begin());

    }

}

return Max;

\(multiset\) 版：时间复杂度 \(O(nlog^2n)\)

\(vector\) 版：时间复杂度 \(O(n^2logn)\)

备注：如果数据是随机的，\(vector\) 的写法会很快，但菊花图可以把它卡掉

然后 \(tgD1T3\) 就被我们解决了

还有就是那个二分上界可以换成树的直径

\(Code\ Below:\)

#include <bits/stdc++.h>

using namespace std;

const int maxn=50000+10;

int n,m,head[maxn],tot,ans,up;

struct node{

    int to,next,val;

}e[maxn<<1];

multiset<int> s[maxn];

multiset<int>::iterator it;

inline int read(){

    register int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

    return (f==1)?x:-x;

}

inline void add(int x,int y,int w){

    e[++tot].to=y;

    e[tot].val=w;

    e[tot].next=head[x];

    head[x]=tot;

}

int dfs(int x,int fa,int k){

    s[x].clear();

    int val;

    for(int i=head[x],y;i;i=e[i].next){

        y=e[i].to;

        if(y==fa) continue;

        val=dfs(y,x,k)+e[i].val;

        if(val>=k) ans++;

        else {

            s[x].insert(val);

        }

    }

    int Max=0;

    while(!s[x].empty()){

        if(s[x].size()==1){

            return max(Max,*s[x].begin());

        }

        it=s[x].lower_bound(k-*s[x].begin());

        if(it==s[x].begin()&&s[x].count(*it)==1) it++;

        if(it==s[x].end()){

            Max=max(Max,*s[x].begin());

            s[x].erase(s[x].find(*s[x].begin()));

        }

        else {

            ans++;

            s[x].erase(s[x].find(*it));

            s[x].erase(s[x].find(*s[x].begin()));

        }

    }

    return Max;

}

int check(int k){

    ans=0;

    dfs(1,0,k);

    if(ans>=m) return 1;

    return 0;

}

int dfs1(int x,int fa){

    int sum1=0,sum2=0;

    for(int i=head[x],y;i;i=e[i].next){

        y=e[i].to;

        if(y==fa) continue;

        sum2=max(sum2,dfs1(y,x)+e[i].val);

        if(sum1<sum2) swap(sum1,sum2);

    }

    up=max(up,sum1+sum2);

    return sum1;

}

int main()

{

    n=read(),m=read();

    int x,y,w;

    for(int i=1;i<n;i++){

        x=read(),y=read(),w=read();

        add(x,y,w);add(y,x,w);

    }

    dfs1(1,0);

    int l=1,r=up,mid;

    while(l<r){

        mid=l+r+1>>1;

        if(check(mid)) l=mid;

        else r=mid-1;

    }

    printf("%d\n",l);

    return 0;

}

巴特西

[NOIP2018]赛道修建（二分+multiset）

1、 \(b_i=a_i+1\) 的情况（一条链）

2、 \(m=1\) 的情况（树的直径）

3、\(a_i=1\)的情况（菊花图）

最新文章

热门文章