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

题目

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

样例说明
奶牛1和奶牛3参与值班即可．

HINT

Source

Silver

题解

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

代码

 /*Author:WNJXYK*/

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int n,st,ed;

 struct line{

     int left,right;

     int w;

 }cow[];

 bool cmp(line a,line b){

     if (a.left<b.left) return true;

     if (a.left==b.left && a.right<b.right) return true;

     return false;

 }

 inline int remin(int a,int b){

     if (a<b) return a;

     return b;

 }

 inline int remax(int a,int b){

     if (a>b) return a;

     return b;

 }

 const int Maxn=;

 const int Inf=;

 struct Btree{

     int left,right;

     int min;

     int tag;

 }tree[Maxn*+];

 void build(int x,int left,int right){

     tree[x].left=left;

     tree[x].right=right;

     tree[x].tag=Inf;

     if (left==right){

         tree[x].min=(left<st?:Inf);

     }else{

         int mid=(left+right)/;

         build(x*,left,mid);

         build(x*+,mid+,right);

         tree[x].min=remin(tree[x*].min,tree[x*+].min);

     }

 }

 inline void clean(int x){

     if (tree[x].left!=tree[x].right){

         tree[x*].min=remin(tree[x].tag,tree[x*].min);

         tree[x*].tag=remin(tree[x].tag,tree[x*].tag);

         tree[x*+].min=remin(tree[x].tag,tree[x*+].min);

         tree[x*+].tag=remin(tree[x].tag,tree[x*+].tag);

         tree[x].tag=Inf;

     }

 }

 void change(int x,int left,int right,int val){

     clean(x);

     if (left<=tree[x].left && tree[x].right<=right){

         tree[x].tag=remin(tree[x].tag,val);

         tree[x].min=remin(tree[x].min,val);

     }else{

         int mid=(tree[x].left+tree[x].right)/;

         if (left<=mid) change(x*,left,right,val);

         if (right>=mid+)change(x*+,left,right,val);

         tree[x].min=remin(tree[x*].min,tree[x*+].min);

     }

 }

 int query(int x,int left,int right){

     clean(x);

     if (left<=tree[x].left && tree[x].right<=right){

         return tree[x].min;

     }else{

         int Ans=Inf;

         int mid=(tree[x].left+tree[x].right)/;

         if (left<=mid) Ans=remin(Ans,query(x*,left,right));

         if (right>=mid+) Ans=remin(Ans,query(x*+,left,right));

         return Ans;

     }

 }

 int main(){

     scanf("%d%d",&n,&ed);

     st=;

     build(,,ed);

     for (int i=;i<=n;i++){

         scanf("%d%d",&cow[i].left,&cow[i].right);

         cow[i].w=;

     }

     sort(cow+,cow+n+,cmp);

     for (int i=;i<=n;i++){

         int mindist=query(,remax(cow[i].left-,),cow[i].right)+cow[i].w;

         //printf("mindist:%d\n",mindist);

         //printf("query %d %d -> min=%d\n",remax(cow[i].left-1,0),cow[i].right,query(1,cow[i].left,cow[i].right));

         change(,cow[i].left,cow[i].right,mindist);

     }

         //printf("query min=%d\n",query(1,ed,ed));

     int ans=query(,ed,ed);

     if (ans==Inf)

         printf("-1\n");

     else

         printf("%d\n",ans);

     return ;

 }

秒客网