Luogu P2970 이기 적 인 방목 + 선분 커버

제목 의 대의
FJ 는 한 무리의 소 들 이 있 는데, 그들 은 특정한 곳 에서 만 풀 을 먹 는 것 을 좋아한다.지금 당신 에 게 범 위 를 주 겠 습 니 다. 최대 몇 마리 의 Cow 가 동시에 풀 을 먹 을 수 있 기 를 바 랍 니 다.
분석 하 다.
이 문 제 는 사실 선분 커버 문제 와 유사 하 다.생각 을 조금 만 생각해 보면 나 올 수 있 습 니 다. 먼저 여러 키워드 로 정렬 (뒤에 점 이 앞 에 있 고 길이 가 길 어 요) 한 다음 에 첫 번 째 소 부터 욕심 을 부리 기 시 작 했 습 니 다. 공공 부분 만 없 으 면 ans + + 를 기록 한 다음 에 그 소 가 '욕심' 을 부 렸 습 니 다.
코드
#include
#include
#include
#include
#include
#include
using namespace std;
int i,m,n,j,k,s=1,take=1;
struct cow{
    int s,e;
}a[50001];
bool cmp(cow a,cow b){
    return (a.eint main(){
    cin>>n;
    for(i=1;i<=n;i++)
        scanf("%d%d",&a[i].s,&a[i].e);
    sort(a+1,a+1+n,cmp);
    for(i=2;i<=n;i++)
        if(a[i].s>=a[take].e)s++,take=i;
    cout<return 0;
}

총결산
이런 욕심 은 사실 비교적 간단 하지만 젖소 가 풀 을 먹 는 범 위 를 선분 으로 이해 해 야 가짜 '선분 커버' 로 할 수 있다. 즉, 문 제 를 풀 때 사고방식 이 죽 으 면 안 된다 는 것 이다.

좋은 웹페이지 즐겨찾기