题目链接

Intervals

题目描述

You are given $n$ closed, integer intervals $[a_i,b_i]$ and $n$ integers $c_1$, ...,$c_n$.
Write a program that:
reads the number of intervals, their end points and integers $c_1$, ...,$c_n$ from the standard input,
computes the minimal size of a set $Z$ of integers which has at least $c_i$ common elements with interval $[a_i,b_i]$, for each $i=1,2$,...,$n$,
writes the answer to the standard output.

输入格式

The first line of the input contains an integer $n$ ($1 \le n \le 50000$) -- the number of intervals. The following n lines describe the intervals. The ($i+1$)-th line of the input contains three integers $a_i$, $b_i$ and $c_i$ separated by single spaces and such that $0 \le a_i \le b_i \le 50000$ and $1 \le c_i \le b_i-a_i+1$.

输出格式

The output contains exactly one integer equal to the minimal size of set $Z$ sharing at least $c_i$ elements with interval $[a_i, b_i]$, for each $i=1,2$,...,$n$.

样例输入

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

样例输出

6

题解

题意:给定$n$个条件,要求区间$[a_i,b_i]$之间至少有$c_i$个元素,$0 \le c_i \le b_i-a_i+1$,求最少有多少个元素。
我们令$s[i]$表示小于等于$i$的元素有多少个。
那么对于每个约束条件,就有$s[b_i]-s[a_i-1] \ge c_i$。
也就是$s[b_i]+$($-c_i$)$\ge s[a_i-1]$
这个式子和最短路的式子是一样的,所以我们可以建一条$s[b_i]$到$s[a_i-1]$长度为$c_i$的边。
但是我们发现这张图是不完整的。
所以我们还要加上一些隐藏条件。

  • $s[i]-s[i-1] \ge 0$
    $\rightarrow s[i]+0 \ge s[i-1]$
  • $s[i]-s[i-1] \le 1$
    $\rightarrow s[i-1]+1 \ge s[i]$

所以我们加上$s[i]$到$s[i-1]$长度为$0$的边,
$s[i-1]$到$s[i]$长度为$1$的边。
假设最大值为$mx$,接下来来我们跑$s[mx]$到$s[0]$的最短路,答案就是$s[mx]-s[0]$。
上代码:

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int x,y,c;
struct aa{
    int to,nxt,v;
}p[500009];
int h[50009],len;
int mx;
int s[50009];
void add(int u,int v,int w){
    p[++len].to=v;
    p[len].v=w;
    p[len].nxt=h[u];
    h[u]=len;
}
bool k[50009];
void dfs(int u){
    int q[500009],l=0,r=0;
    q[0]=u;
    while(l!=r+1){
        u=q[l];
        l++;l%=500000;
        k[u]=0;
        for(int j=h[u];j;j=p[j].nxt){
            if(s[p[j].to]>s[u]+p[j].v){
                s[p[j].to]=s[u]+p[j].v;
                r++;
                r%=500000;//循环队列
                if(!k[p[j].to]) q[r]=p[j].to;
                k[p[j].to]=1;
            }
        }
    }
}
int main(){
    while(scanf("%d",&n)!=EOF){
        memset(s,1,sizeof(s));
        memset(h,0,sizeof(h));
        len=0;
        for(int j=1;j<=n;j++){
            scanf("%d%d%d",&x,&y,&c);
            x++;y++;
            mx=max(mx,y);
            add(y,x-1,-c);
        }
        for(int j=1;j<=mx;j++){
            add(j-1,j,1);
            add(j,j-1,0);
        }
        s[mx]=0;
        dfs(mx);
        printf("%d\n",-s[0]);
    }
    return 0;
}