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
1 7
3 6
6 10
Sample Output
2
样例说明
奶牛1和奶牛3参与值班即可．
HINT
Source
题解：
此题<清理牛棚 线段树而已
代码：
#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
代码：（copy）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define pa pair<int,int>
#define inf 1000000000
#define ll long long
using namespace std;
inline int read()
{
int x=;char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x;
}
int n,T,cnt;
bool vis[];
int dis[],last[];
struct data{int to,next,v;}e[];
void insert(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
}
void dijkstra()
{
priority_queue<pa,vector<pa>,greater<pa> >q;
for(int i=;i<=T;i++)dis[i]=inf;
dis[]=;q.push(make_pair(,));
while(!q.empty())
{
int now=q.top().second;q.pop();
if(vis[now])continue;vis[now]=;
for(int i=last[now];i;i=e[i].next)
if(dis[now]+e[i].v<dis[e[i].to])
{
dis[e[i].to]=dis[now]+e[i].v;
q.push(make_pair(dis[e[i].to],e[i].to));
}
}
}
int main()
{
n=read();T=read();
for(int i=;i<=T;i++)
insert(i,i-,);
for(int i=;i<=n;i++)
{
int a=read(),b=read();
insert(a-,b,);
}
dijkstra();
if(dis[T]==inf)puts("-1");
else printf("%d\n",dis[T]);
return ;
}