自动搬运

查看原文

来自洛谷，原作者为

	微香玉烛暗 逆鳞 别碰哦

搬运于2025-08-24 21:43:58，当前版本为作者最后更新于2019-09-22 16:16:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道关于区间的简单贪心，但是有些迷惑性。很多人一看到题目就把数据按左端点排序，但是应当按右边端点，因为要求最多牛吃草时刻，所以看这头牛的结束时间，每次用开始时间比较，并更新$ans$。（初值为$1$）

没听懂？
没关系，结合数据一起分析：

2 4 
1 12 
4 5 
7 10 
7 8 

排序后就成了

2 4 
4 5 
7 8
7 10 
1 12 

$now$初始值为$4$，$ans=1$，从第二个开始枚举。
① $4>=4$，所以$now=5$，$ans++$
② $7>=5$，所以$now=8$，$ans++$
③ $7<8$，不变
④ $7<8$，不变
⑤ $1<8$，不变

$ans=3$

# include <cstdio>
# include <iostream>
# include <algorithm>
using namespace std;
const int N=50005;
int n,ans=1,now;

struct node {
	int x,y;
	friend bool operator < (const node &p,const node &q) {
		return p.y<q.y;
	}
}a[N];

/*
另一种写法cmp
bool cmp (node x,node y) {
    return x.y<y.y;
}
*/

int main () {
	scanf ("%d",&n);
	for (int i=1;i<=n;i++)
		scanf ("%d%d",&a[i].x,&a[i].y);
	sort (a+1,a+1+n);
	now=a[1].y;
	for (int i=2;i<=n;i++) {
		if (a[i].x>=now) {
			ans++;
			now=a[i].y;
		}
	}//如上分析代码实现
	printf ("%d\n",ans);
	return 0;
}
//By苍空的蓝耀