题解 P2970 【[USACO09DEC]自私的放牧Selfish Grazing】

· · 题解

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

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

2 4 
1 12 
4 5 
7 10 
7 8

排序后就成了

2 4 
4 5 
7 8
7 10 
1 12
① $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苍空的蓝耀