BZOJ 3410: [Usaco2009 Dec]Selfish Grazing 自私的食草者(贪心)

时间:2021-11-24 23:11:58

这= =,就是线段覆盖对了= =直接贪心就行了= =

CODE:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
 int l,r;
}a[50010];
int r,ans,n;
bool cmp(node x,node y){
 if (x.l==y.l) return x.r<y.r;
 return x.l<y.l;
}
int main(){
 scanf("%d",&n);
 for (int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r);
 sort(a+1,a+1+n,cmp);
 r=0;
 for (int i=1;i<=n;i++) {
  if (a[i].r<r) r=a[i].r;
  if (a[i].l>=r) {ans++;r=a[i].r;}
 }
 printf("%d",ans);
 return 0;
}