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

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

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 45 Solved: 26
[Submit][Status]

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

题解：此题<清理牛棚线段树而已代码：

  #include<cstdio>
 #include<cstdlib>
 #include<cmath>
 #include<cstring>
 #include<algorithm>
 #include<iostream>
 #include<vector>
 #include<map>
 #include<set>
 #include<queue>
 #include<string>
 #define inf 1000000000
 #define maxn 1000000+10000
 #define maxm 500+100
 #define eps 1e-10
 #define ll long long
 #define pa pair<int,int>
 #define for0(i,n) for(int i=0;i<=(n);i++)
 #define for1(i,n) for(int i=1;i<=(n);i++)
 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 #define mod 1000000007
 using namespace std;
 inline int read()
 {
     int x=,f=;char ch=getchar();
     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
     return x*f;
 }
 struct rec{int l,r;}a[maxn];
 struct seg{int l,r,mi,tag;}t[*maxn];
 int n,m;
 inline bool cmp(rec a,rec b)
 {
     return a.l<b.l||(a.l==b.l&&a.r<b.r);
 }
 inline void pushup(int k)
 {
     t[k].mi=min(t[k<<].mi,t[k<<|].mi);
 }
 inline void update(int k,int z)
 {
     t[k].mi=min(t[k].mi,z);
     t[k].tag=min(t[k].tag,z);
 }
 inline void pushdown(int k)
 {
     if(t[k].tag==inf)return ;
     update(k<<,t[k].tag);
     update(k<<|,t[k].tag);
     t[k].tag=inf;
 }
 inline void build(int k,int x,int y)
 {
     int l=t[k].l=x,r=t[k].r=y,mid=(l+r)>>;t[k].tag=inf;
     if(l==r){t[k].mi=l==?:inf;return ;}
     build(k<<,l,mid);build(k<<|,mid+,r);
     pushup(k);
 }
 inline ll query(int k,int x)
 {
     int l=t[k].l,r=t[k].r,mid=(l+r)>>;
     if(l==r)return t[k].mi;
     pushdown(k);
     if(x<=mid)return query(k<<,x);else return query(k<<|,x);
 }
 inline void change(int k,int x,int y,int z)
 {
     int l=t[k].l,r=t[k].r,mid=(l+r)>>;
     if(l==x&&r==y){update(k,z);return;}
     pushdown(k);
     if(y<=mid)change(k<<,x,y,z);
     else if(x>mid)change(k<<|,x,y,z);
     else change(k<<,x,mid,z),change(k<<|,mid+,y,z);
     pushup(k);
 }
 int main()
 {
     freopen("input.txt","r",stdin);
     freopen("output.txt","w",stdout);
     n=read();m=read();
     for1(i,n)a[i].l=read(),a[i].r=read();
     sort(a+,a+n+,cmp);
     build(,,m);
     for1(i,n)
     {
         ll t=query(,a[i].l-);
         if(t!=inf)change(,a[i].l,a[i].r,t+);else break;
     }
     ll ans=query(,m);
     printf("%lld\n",ans==inf?-:ans);
     return ;
 }

差了题解发现居然还有贪心做法：

iwtwiioi：

显然左端点排序后，依次取。

要考虑下一次取的方案：

待选点为a[j].x<=a[now].y+1的所有点j，其中now是当前所选

那么我们要在这些点内做决策

贪心就是取y最大的待选点，即

max(a[j].y)的j

orzzzzzzzzzz

代码：（copy）

 #include <cstdio>
 #include <cstring>
 #include <cmath>
 #include <string>
 #include <iostream>
 #include <algorithm>
 #include <queue>
 using namespace std;
 #define rep(i, n) for(int i=0; i<(n); ++i)
 #define for1(i,a,n) for(int i=(a);i<=(n);++i)
 #define for2(i,a,n) for(int i=(a);i<(n);++i)
 #define for3(i,a,n) for(int i=(a);i>=(n);--i)
 #define for4(i,a,n) for(int i=(a);i>(n);--i)
 #define CC(i,a) memset(i,a,sizeof(i))
 #define read(a) a=getint()
 #define print(a) printf("%d", a)
 #define dbg(x) cout << #x << " = " << x << endl
 #define printarr2(a, b, c) for1(i, 1, b) { for1(j, 1, c) cout << a[i][j]; cout << endl; }
 #define printarr1(a, b) for1(i, 1, b) cout << a[i]; cout << endl
 inline const int getint() { int r=, k=; char c=getchar(); for(; c<''||c>''; c=getchar()) if(c=='-') k=-; for(; c>=''&&c<=''; c=getchar()) r=r*+c-''; return k*r; }
 inline const int max(const int &a, const int &b) { return a>b?a:b; }
 inline const int min(const int &a, const int &b) { return a<b?a:b; } const int N=;
 int n, t, cnt;
 struct dat { int x, y; }a[N];
 bool cmp(const dat &a, const dat &b) { return a.x==b.x?a.y<b.y:a.x<b.x; } int main() {
     read(n); read(t);
     for1(i, , n) read(a[i].x), read(a[i].y);
     sort(a+, a++n, cmp);
     a[n+].x=;
     for1(i, , n) if(a[i].x!=a[i+].x) a[++cnt]=a[i];
     if(a[].x>) { puts("-1"); return ; }
     int ans=, now=;
     for1(i, , cnt) {
         int fix=, nx=now, pos=, ed=a[now].y;
         while(nx<cnt && a[nx+].x<=ed+) {
             ++nx;
             if(a[nx].y>ed && fix<a[nx].y) {
                 fix=a[nx].y;
                 pos=nx;
             }
         }
         if(a[now].y==t) break;
         if(nx==now || fix==) { puts("-1"); return ; }
         now=pos;
         i=nx;
         ++ans;
     }
     if(a[now].y!=t) puts("-1");
     else print(ans);
     return ;
 }

卧槽，这题居然还能用最短路解，是有多少做法233333