bzoj3389 [Usaco2004 Dec]Cleaning Shifts安排值班-白红宇

bzoj3389 [Usaco2004 Dec]Cleaning Shifts安排值班

阅读量：5052 次

发布时间：2019-06-12

本文共 1052 字，大约阅读时间需要 3 分钟。

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参与值班即可．

原来想的是dp，结果发现T来T去的在T

后来想了一下是贪心

假设当前已经覆盖了1到l

那么找左节点<=l的右节点最大的r,令l=max(l,a[i].r)，然后继续

wa了几次……因为以为左节点大的一定右节点大，实际上这显然不正确

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #define LL long long#define inf 0x7ffffff#define pa pair
                
                 using namespace std;pa a[25010];int n,m,now,ans,l;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}inline bool cmp(const pa &a,const pa &b){return a.first
                 
                  
                   l+1) { printf("-1"); return 0; } ans++; } if (l

转载于:https://www.cnblogs.com/zhber/p/4035898.html

你可能感兴趣的文章

JavaScript入门经典红皮书阅读笔记6.13（第二篇）