【BZOJ】3389: [Usaco2004 Dec]Cleaning Shifts安排值班（贪心）

http://www.lydsy.com/JudgeOnline/problem.php?id=3389

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

要考虑下一次取的方案：

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

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

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

max(a[j].y)的j

实现中细节太多QAQ，写了挺久的。。

#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=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; }

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=25005;

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, 1, n) read(a[i].x), read(a[i].y);

	sort(a+1, a+1+n, cmp);

	a[n+1].x=100055050;

	for1(i, 1, n) if(a[i].x!=a[i+1].x) a[++cnt]=a[i];

	if(a[1].x>1) { puts("-1"); return 0; }

	int ans=1, now=1;

	for1(i, 1, cnt) {

		int fix=0, nx=now, pos=0, ed=a[now].y;

		while(nx<cnt && a[nx+1].x<=ed+1) {

			++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==0) { puts("-1"); return 0; }

		now=pos;

		i=nx;

		++ans;

	}

	if(a[now].y!=t) puts("-1");

	else print(ans);

	return 0;

}

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