Luogu P2970 이기 적 인 방목 + 선분 커버
2127 단어 총결산제목 테이프알고리즘/데이터 구조
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;
}
총결산
이런 욕심 은 사실 비교적 간단 하지만 젖소 가 풀 을 먹 는 범 위 를 선분 으로 이해 해 야 가짜 '선분 커버' 로 할 수 있다. 즉, 문 제 를 풀 때 사고방식 이 죽 으 면 안 된다 는 것 이다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Java 기본 사용법 요약 (2)StringBuilder 또는 StringBuffer를 사용할 때 append () 방법으로 텍스트를 추가하고 toString () 방법으로 연결된 전체 텍스트를 가져올 수 있습니다 3. Iterator를 사용합니다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.