POJ2376 Cleaning Shifts

Cleaning Shifts

• 分析

  此类问题似被统称为——最小区间覆盖问题。
  首先考虑最简单的转移方程
  
  表示覆盖[1,b[i]]的区间的最小代价。
  考虑优化——快速找到区间最小值。只需要建立一棵线段树，每次查询对应区间，更新。

• 代码

//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")

/*
    区间最小覆盖问题

    设f[x]覆盖[1,x]的最小花费,那么

把所有牛的上班时间按照右端点从大到

小排序,那么这个转移来自[s[i].l,s[i-1].r] 
*/
#include<bits/stdc++.h>

#define R register
#define ll long long
#define inf INT_MAX

#define ls now<<1
#define rs ls|1

using namespace std;

const int N=3e4+10,M=1e6+10;

int n,en,tot;
int f[N],k[M<<2];

struct nkl
{
    int x,y;
}s[N];

inline bool god(nkl xx,nkl yy)
{
    return xx.y<yy.y;
}

inline void build(int now,int l,int r)
{
    if(l==r)
    {
        k[now]=1e9;
        return ;
    }

    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);

    k[now]=min(k[ls],k[rs]);
}

inline void add(int now,int l,int r,int x,int z)
{
    if(l==r)
    {
        k[now]=min(k[now],z);
        return ;
    }

    int mid=(l+r)>>1;
    if(x<=mid) add(ls,l,mid,x,z);
    else add(rs,mid+1,r,x,z);

    k[now]=min(k[ls],k[rs]);
}

inline int find(int now,int l,int r,int x,int y)
{
    if(x>y) return 1e9;
    if(l>=x&&r<=y) return k[now];

    int mid=(l+r)>>1,ret=1e9;
    if(x<=mid) ret=find(ls,l,mid,x,y);
    if(mid<y) ret=min(ret,find(rs,mid+1,r,x,y));

    return ret;
}

int main()
{
    scanf("%d%d",&n,&en);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&s[i].x,&s[i].y);
    sort(s+1,s+n+1,god);

    build(1,0,en);add(1,0,en,0,0);
    for (int i=1;i<=n;i++)
    {
        int l=max(s[i].x-1,0),r=min(en,s[i].y);
        int now=find(1,0,en,l,r);
        if(now>1e9) continue;
        add(1,0,en,r,now+1);
    }

    int ans=find(1,0,en,en,en);
    if(ans>1e8) puts("-1");
    else printf("%d\n",ans);

    return 0;
}