3389: [Usaco2004 Dec]Cleaning Shifts安排值班

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 367  Solved: 141

[][][]

Description

    一天有T(1≤T≤10^6)个时段．约翰正打算安排他的N(1≤N≤25000)只奶牛来值班，打扫

打扫牛棚卫生．每只奶牛都有自己的空闲时间段[Si，Ei](1≤Si≤Ei≤T)，只能把空闲的奶牛安排出来值班．而且，每个时间段必需有奶牛在值班．  那么，最少需要动用多少奶牛参与值班呢？如果没有办法安排出合理的方案，就输出-1.

Input

 

    第1行：N，T．

    第2到N+1行：Si，Ei．

Output

 

    最少安排的奶牛数．

Sample Input

3 10

1 7

3 6

6 10

Sample Output

2

样例说明

奶牛1和奶牛3参与值班即可．

HINT

 

Source

yy了一个线段树dp做法就过了。。。挖个坑 不知道为什么是对的（大水题都不会可以持矢了）

#include 
       
        using namespace std;const int N = 1000010, inf = 0x3f3f3f3f;struct line {    int l, r;} x[N];int n, t;int dp[N] ,tree[N << 2];bool cp(line x, line y){    if(x.l != y.l) return x.l < y.l;    return x.r > y.r;}void update(int l, int r, int x, int pos, int num){    if(l == r)    {        tree[x] = min(tree[x], num);        return;    }    int mid = (l + r) >> 1;    if(pos <= mid) update(l ,mid ,x << 1 , pos, num);    else update(mid + 1, r, x << 1 | 1, pos, num);    tree[x] = min(tree[x << 1], tree[x << 1 | 1]);}int query(int l, int r, int x, int a, int b){    if(l > b || r < a) return inf;    if(l >= a && r <= b) return tree[x];    int mid = (l + r) >> 1;    return min(query(l, mid, x << 1, a, b) ,query(mid + 1, r, x << 1 | 1, a, b));}int main(){    memset(tree, 0x3f3f, sizeof(tree));    memset(dp, 0x3f3f, sizeof(dp));    scanf("%d%d", &n ,&t);    for(int i = 1; i <= n; ++i) scanf("%d%d", &x[i].l, &x[i].r);    sort(x + 1, x + n + 1, cp);    if(x[1].l != 1)    {        puts("-1");        return 0;    }    dp[x[1].r] = 1; update(1, t, 1, x[1].r, 1);    for(int i = 2; i <= n; ++i)    {        int l = x[i].l, r = x[i].r;        dp[r] = min(dp[r], query(1, t, 1, l - 1, r) + 1);        update(1, t, 1, r, dp[r]);    }    printf("%d\n", dp[t] > n ? -1 : dp[t]);    return 0;}