首页 > 代码库 > BZOJ 3389: [Usaco2004 Dec]Cleaning Shifts安排值班

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

2024-07-31 07:00:46   214人阅读

题目

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

Time Limit: 1 Sec  Memory Limit: 128 MB

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

Silver

题解

呵呵，做了一半忽然发现这不是昨天做的那题（BZOJ 1672）的减弱版，题解直接见http://www.cnblogs.com/WNJXYK/p/4074788.html。线段树动态规划！【听说贪心可做，Orz但那是我N^2贪心TLE了两次、、、

代码

  1 /*Author:WNJXYK*/  2 #include<cstdio>  3 #include<algorithm>  4 using namespace std;  5   6 int n,st,ed;  7 struct line{  8     int left,right;  9     int w; 10 }cow[25010]; 11 bool cmp(line a,line b){ 12     if (a.left<b.left) return true; 13     if (a.left==b.left && a.right<b.right) return true; 14     return false; 15 } 16 inline int remin(int a,int b){ 17     if (a<b) return a; 18     return b;     19 } 20 inline int remax(int a,int b){ 21     if (a>b) return a; 22     return b; 23 } 24  25 const int Maxn=1000000; 26 const int Inf=2000000000; 27 struct Btree{ 28     int left,right; 29     int min; 30     int tag; 31 }tree[Maxn*4+10]; 32  33 void build(int x,int left,int right){ 34     tree[x].left=left; 35     tree[x].right=right; 36     tree[x].tag=Inf; 37     if (left==right){ 38         tree[x].min=(left<st?0:Inf); 39     }else{ 40         int mid=(left+right)/2; 41         build(x*2,left,mid); 42         build(x*2+1,mid+1,right); 43         tree[x].min=remin(tree[x*2].min,tree[x*2+1].min); 44     } 45 } 46  47 inline void clean(int x){ 48     if (tree[x].left!=tree[x].right){ 49         tree[x*2].min=remin(tree[x].tag,tree[x*2].min); 50         tree[x*2].tag=remin(tree[x].tag,tree[x*2].tag); 51         tree[x*2+1].min=remin(tree[x].tag,tree[x*2+1].min); 52         tree[x*2+1].tag=remin(tree[x].tag,tree[x*2+1].tag); 53         tree[x].tag=Inf; 54     } 55 } 56  57 void change(int x,int left,int right,int val){ 58     clean(x); 59     if (left<=tree[x].left && tree[x].right<=right){ 60         tree[x].tag=remin(tree[x].tag,val); 61         tree[x].min=remin(tree[x].min,val); 62     }else{ 63         int mid=(tree[x].left+tree[x].right)/2; 64         if (left<=mid) change(x*2,left,right,val); 65         if (right>=mid+1)change(x*2+1,left,right,val); 66         tree[x].min=remin(tree[x*2].min,tree[x*2+1].min); 67     } 68 } 69  70 int query(int x,int left,int right){ 71     clean(x); 72     if (left<=tree[x].left && tree[x].right<=right){ 73         return tree[x].min; 74     }else{ 75         int Ans=Inf; 76         int mid=(tree[x].left+tree[x].right)/2; 77         if (left<=mid) Ans=remin(Ans,query(x*2,left,right)); 78         if (right>=mid+1) Ans=remin(Ans,query(x*2+1,left,right)); 79         return Ans;  80     } 81 } 82  83  84 int main(){ 85     scanf("%d%d",&n,&ed); 86     st=1; 87     build(1,0,ed); 88     for (int i=1;i<=n;i++){ 89         scanf("%d%d",&cow[i].left,&cow[i].right); 90         cow[i].w=1; 91     } 92     sort(cow+1,cow+n+1,cmp); 93     for (int i=1;i<=n;i++){ 94         int mindist=query(1,remax(cow[i].left-1,0),cow[i].right)+cow[i].w; 95         //printf("mindist:%d\n",mindist); 96         //printf("query %d %d -> min=%d\n",remax(cow[i].left-1,0),cow[i].right,query(1,cow[i].left,cow[i].right)); 97         change(1,cow[i].left,cow[i].right,mindist); 98     }  99         //printf("query min=%d\n",query(1,ed,ed));100     int ans=query(1,ed,ed);101     if (ans==Inf)102         printf("-1\n");103     else104         printf("%d\n",ans); 105     return 0;106 }
View Code

 

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


联系
我们