1 条题解

  • 1
    @ 2017-10-03 19:08:55

    看到此题,首先第一是一个贪心思路:先到终点的小怪物优先上车。很容易证明其正确性:如果有两只小怪物都要经过同一个点,那么如果让终点在前的小怪物优先上车,能更早的下车,为后面的小怪物腾出座位;如果让终点在后的小怪物优先上车,则可能堵住后面的怪物的位置,并且这两种策略对答案的贡献是相同的,故终点在前怪物先上。证毕。
    可以看出,以上优先顺序与怪物的上车位置无关,只与终点有关。故只需要按终点排序,再来按上述贪心策略进行操作。
    关于操作,可以得到每一队小怪物的上车数为mim(车满载量-起点到终点段最大的一个车上已占座位数,这一队怪物的总数);
    于是我考试时傻B的想出了如下错误方法(区间修改点查询树状数组)
    #include<bits/stdc++.h>
    const int maxn=2e5;
    inline const void read(int &a)
    {
    a=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')
    {
    a=(a<<1)+(a<<3)+c-'0';
    c=getchar();
    }
    }
    inline const int lowbit(int a)
    {
    return a&(-a);
    }
    int k,n,m,more[maxn],ans=0;
    struct team
    {
    int start,end,num;
    }t[maxn];
    inline const bool comp(const team&a,const team&b)
    {
    if(a.end<b.end)return true;
    else return false;
    }
    inline const void modify(int a,int b)
    {
    while(a<=n)
    {
    more[a]+=b;
    a+=lowbit(a);
    }
    }
    inline const int query(int a)
    {
    int ans=0;
    while(a)
    {
    ans+=more[a];
    a-=lowbit(a);
    }
    return ans;
    }
    int main()
    {
    memset(more,0,sizeof(more));
    read(k);read(n);read(m);
    for(int i=1;i<=k;i++){read(t[i].start);read(t[i].end);read(t[i].num);}
    std::sort(t+1,t+1+k,comp);
    for(int i=1;i<=k;i++)
    {
    int load=std::min(m-query(问题所在,不会表示区间最值(当然是可以做的)),t[i].num);
    ans+=load;
    if(load)modify(t[i].start,load);modify(t[i].end,-load);
    }
    std::cout<<ans;
    return 0;
    }
    发现问题为时已晚,只有用了一个类似于单调队列的东西拿了30分。
    正解
    由于上述问题:不可忽略区间最值查询,故树状数组是远远不够用的。还是不能为了简单就直接思考不完善的方法,不能怕麻烦:

    #include<bits/stdc++.h>
    inline const void read(int &a)
    {
        a=0;char c=getchar();
        while(c<'0'||c>'9')c=getchar();
        while(c>='0'&&c<='9')
        {
            a=(a<<1)+(a<<3)+c-'0';
            c=getchar();
        }
    }
    const int maxn=2e5;
    int limit[maxn],lazy[maxn];
    inline const void update(int p)
    {
        limit[p]=std::max(limit[p<<1],limit[p<<1|1]);
    }
    inline const void push_col(int p)
    {
        if(lazy[p])
        {
            limit[p<<1]+=lazy[p];limit[p<<1|1]+=lazy[p];
            lazy[p<<1]+=lazy[p];lazy[p<<1|1]+=lazy[p];
            lazy[p]=0;
        }
    }
    inline const int query(int p,int l,int r,int ll,int rr)
    {
        if(l>rr||r<ll)return 0;
        if(l>=ll&&r<=rr)return limit[p];
        push_col(p);
        int mid=(l+r)>>1,ans=std::max(query(p<<1,l,mid,ll,rr),query(p<<1|1,mid+1,r,ll,rr));
        return ans;
    }
    inline const void modify(int p,int l,int r,int ll,int rr,int mark)
    {
        if(l>rr||r<ll)return ;
        if(l>=ll&&r<=rr){lazy[p]+=mark;limit[p]+=mark;return ;}
        push_col(p);
        int mid=(l+r)>>1;
        modify(p<<1,l,mid,ll,rr,mark);modify(p<<1|1,mid+1,r,ll,rr,mark);
        update(p);
    }
    struct team
    {
        int start,end,num;
    }t[maxn];
    inline const bool comp(const team&a,const team&b)
    {
        if(a.end<b.end)return true;
        return false;
    }
    int main()
    {
        memset(limit,0,sizeof(limit));
        int k,n,m,ans=0;
        read(k);read(n);read(m);
        for(int i=1;i<=k;i++){read(t[i].start);read(t[i].end);read(t[i].num);}
        std::sort(t+1,t+1+k,comp);
        for(int i=1;i<=k;i++)
        {
            int load=std::min(m-query(1,1,n,t[i].start,t[i].end-1),t[i].num);
            if(load)modify(1,1,n,t[i].start,t[i].end-1,load);
            ans+=load;
        }
        std::cout<<ans;
        return 0;
    }
    
  • 1

信息

难度
8
分类
(无)
标签
(无)
递交数
23
已通过
4
通过率
17%
上传者