2019暑假集训 Intervals

忘是亡心i 2021-11-29 08:08 319阅读 0赞

--------------------

题目描述

给定n个闭区间\[ai,bi\]和n个整数ci。你需要构造一个整数集合Z，使得对于任意i，Z中满足ai<=x<=bi的x不少于ci个。求Z集合中包含的元素个数的最小值。

输入

第一行为一个整数n（1<=n<=50000)   
接下来n行每行描述一个区间，三个整数分别表示ai，bi和ci。（ 0 <= ai <= bi <= 50000 并且 1 <= ci <= bi - ai+1.）

输出

输出一个整数，表示Z中包含元素个数的最小值。

样例输入

5
    3 7 3
    8 10 3
    6 8 1
    1 3 1
    10 11 1

样例输出

--------------------

由题意我们可以知道
    b[i]-a[i]+1>=c[i]
    两边同时除以-1,
    a[i]-1-b[i]<=-c[i]
    a[i]<=(b[i]+1)+(-c[i]）
    这个式子很熟悉有没有？
    如果没有，看这个
    d[i]<=d[j]+edge(j,i)
    记得这个吗？对于一个无法松弛的单源最短路图，必满足上述关系

--------------------

所以我们在最短路中把（j,i）连边 在本题中将（b[i]+1,a[i]）连边 该过程称为差分约束 用d[i]表示从0-i区间中需要选的数 但是应当注意的是 明显d[0]不一定=0 所以我们需要一个虚拟点作为原点 怎样找这个虚拟点？因为前面有一个(b[i]+1)，当b[i]=max(b[i])时该值最大 所以最短路应当以max(b[i])为原点进行 由题意，在i至i+1区间中，最多选1个数，最少选0个数 于是得到0<=d[i+1]-d[i]<=1 所以同理我们将(i,i-1,0,)以及(i-1,i,1)连边 最后算出d[max(b[i])]即可 上代码

#include<iostream>
    #include<queue>
    #include<cstring>
    using namespace std;
    int n,head[50050],num,a[50050],b[50050],c[50050],d[50050],vst[50050];
    struct edge
    {
        int u,v,c,nxt;
    }e[200050];
    void add(int u,int v,int c)
    {
        e[++num].u=u,e[num].v=v,e[num].c=c;
        e[num].nxt=head[u],head[u]=num;
    }
    void spfa(int x)
    {
        queue<int> q;
        memset(d,127,sizeof d);
        q.push(x);
        d[x]=0;
        vst[x]=1;
        while(!q.empty())
        {
            int xx=q.front();
            q.pop();
            vst[xx]=0;
            for(int st=head[xx];st!=-1;st=e[st].nxt)
            {
                if(d[e[st].v]>e[st].c+d[xx])
                {
                    d[e[st].v]=e[st].c+d[xx];
                    if(!vst[e[st].v])q.push(e[st].v),vst[e[st].v]=1;
                }
            }
        }
    }
    int main()
    {
    //  freopen("in.txt","r",stdin);
    //  freopen("out.txt","w",stdout);
        memset(head,-1,sizeof head);
        scanf("%d",&n);
        int m=-0x3f3f3f3f;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a[i],&b[i],&c[i]);
            add(b[i]+1,a[i],-c[i]);
            m=max(m,b[i]+1);
        }
        for(int i=1;i<=m;i++)
        {
            add(i,i-1,0);
            add(i-1,i,1);
        }
    //  for(int i=1;i<=m;i++)
    //      add(50005,i,0);
    //  for(int i=1;i<=num;i++)
    //      printf("%d %d\n",e[i].u,e[i].v);
        spfa(m);
        int minn=0x3f3f3f3f;
        //for(int i=1;i<=m;i++)minn=min(minn,d[i]);
        printf("%d",-d[0]/*-minn*/);
        return 0;
    }

转载于:https://www.cnblogs.com/qxds/p/11213357.html