首页 > 代码库 > BZOJ3389: [Usaco2004 Dec]Cleaning Shifts安排值班
BZOJ3389: [Usaco2004 Dec]Cleaning Shifts安排值班
3389: [Usaco2004 Dec]Cleaning Shifts安排值班
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 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
2
样例说明
奶牛1和奶牛3参与值班即可．
HINT
Source
Silver
题解：
此题<清理牛棚 线段树而已
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 1000000+1000014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26 int x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 struct rec{int l,r;}a[maxn];32 struct seg{int l,r,mi,tag;}t[4*maxn];33 int n,m;34 inline bool cmp(rec a,rec b)35 {36 return a.l<b.l||(a.l==b.l&&a.r<b.r);37 }38 inline void pushup(int k)39 {40 t[k].mi=min(t[k<<1].mi,t[k<<1|1].mi);41 }42 inline void update(int k,int z)43 {44 t[k].mi=min(t[k].mi,z);45 t[k].tag=min(t[k].tag,z);46 }47 inline void pushdown(int k)48 {49 if(t[k].tag==inf)return ;50 update(k<<1,t[k].tag);51 update(k<<1|1,t[k].tag);52 t[k].tag=inf;53 }54 inline void build(int k,int x,int y)55 {56 int l=t[k].l=x,r=t[k].r=y,mid=(l+r)>>1;t[k].tag=inf;57 if(l==r){t[k].mi=l==0?0:inf;return ;}58 build(k<<1,l,mid);build(k<<1|1,mid+1,r);59 pushup(k);60 }61 inline ll query(int k,int x)62 {63 int l=t[k].l,r=t[k].r,mid=(l+r)>>1;64 if(l==r)return t[k].mi;65 pushdown(k);66 if(x<=mid)return query(k<<1,x);else return query(k<<1|1,x);67 }68 inline void change(int k,int x,int y,int z)69 {70 int l=t[k].l,r=t[k].r,mid=(l+r)>>1;71 if(l==x&&r==y){update(k,z);return;}72 pushdown(k);73 if(y<=mid)change(k<<1,x,y,z);74 else if(x>mid)change(k<<1|1,x,y,z);75 else change(k<<1,x,mid,z),change(k<<1|1,mid+1,y,z);76 pushup(k);77 }78 int main()79 {80 freopen("input.txt","r",stdin);81 freopen("output.txt","w",stdout);82 n=read();m=read();83 for1(i,n)a[i].l=read(),a[i].r=read();84 sort(a+1,a+n+1,cmp);85 build(1,0,m);86 for1(i,n)87 {88 ll t=query(1,a[i].l-1);89 if(t!=inf)change(1,a[i].l,a[i].r,t+1);else break;90 }91 ll ans=query(1,m);92 printf("%lld\n",ans==inf?-1:ans);93 return 0;94 }
差了题解发现居然还有贪心做法：
iwtwiioi：
显然左端点排序后，依次取。
要考虑下一次取的方案：
待选点为a[j].x<=a[now].y+1的所有点j，其中now是当前所选
那么我们要在这些点内做决策
贪心就是取y最大的待选点，即
max(a[j].y)的j
orzzzzzzzzzz
代码：（copy）
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <string> 5 #include <iostream> 6 #include <algorithm> 7 #include <queue> 8 using namespace std; 9 #define rep(i, n) for(int i=0; i<(n); ++i)10 #define for1(i,a,n) for(int i=(a);i<=(n);++i)11 #define for2(i,a,n) for(int i=(a);i<(n);++i)12 #define for3(i,a,n) for(int i=(a);i>=(n);--i)13 #define for4(i,a,n) for(int i=(a);i>(n);--i)14 #define CC(i,a) memset(i,a,sizeof(i))15 #define read(a) a=getint()16 #define print(a) printf("%d", a)17 #define dbg(x) cout << #x << " = " << x << endl18 #define printarr2(a, b, c) for1(i, 1, b) { for1(j, 1, c) cout << a[i][j]; cout << endl; }19 #define printarr1(a, b) for1(i, 1, b) cout << a[i]; cout << endl20 inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }21 inline const int max(const int &a, const int &b) { return a>b?a:b; }22 inline const int min(const int &a, const int &b) { return a<b?a:b; }23 24 const int N=25005;25 int n, t, cnt;26 struct dat { int x, y; }a[N];27 bool cmp(const dat &a, const dat &b) { return a.x==b.x?a.y<b.y:a.x<b.x; }28 29 int main() {30 read(n); read(t);31 for1(i, 1, n) read(a[i].x), read(a[i].y);32 sort(a+1, a+1+n, cmp);33 a[n+1].x=100055050;34 for1(i, 1, n) if(a[i].x!=a[i+1].x) a[++cnt]=a[i];35 if(a[1].x>1) { puts("-1"); return 0; }36 int ans=1, now=1;37 for1(i, 1, cnt) {38 int fix=0, nx=now, pos=0, ed=a[now].y;39 while(nx<cnt && a[nx+1].x<=ed+1) {40 ++nx;41 if(a[nx].y>ed && fix<a[nx].y) {42 fix=a[nx].y;43 pos=nx;44 }45 }46 if(a[now].y==t) break;47 if(nx==now || fix==0) { puts("-1"); return 0; }48 now=pos;49 i=nx;50 ++ans;51 }52 if(a[now].y!=t) puts("-1");53 else print(ans);54 return 0;55 }
BZOJ3389: [Usaco2004 Dec]Cleaning Shifts安排值班
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。