단순 전형 적 인 욕심-(문제 풀이 보고서)HDU 2037--올해 여름 방학 은 AC 가 아 닙 니 다.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 38863 Accepted Submission(s): 20780
문제 설명"올해 여름 방학 은 AC 가 아 닙 니까?""그렇다"고 말 했다."그럼 뭐 하 세 요?"월 드 컵 봐,바보 야!"@#$%^&*%..."
확실히 월 드 컵 이 오고 팬 들 의 명절 도 왔 으 니 많은 ACMer 도 컴퓨터 를 버 리 고 TV 로 달 려 갈 것 으로 보인다.팬 으로서 가능 한 한 많은 완전한 경 기 를 보고 싶 습 니 다.물론 새로운 시대 의 좋 은 청년 으로서 당신 은 반드시 다른 프로그램 을 볼 것 입 니 다.예 를 들 어 뉴스 연합 방송(국가 대사 에 관심 을 가 지 는 것 을 영원히 잊 지 마 세 요),매우 6+7,슈퍼 여자,그리고 왕 씨 가장귀 의 등 입 니 다.만약 에 당신 이 좋아 하 는 모든 텔레비전 프로그램의 중계 시간 표를 알 고 있다 고 가정 하면당신 은 합 리 적 으로 안배 할 수 있 습 니까?목 표 는 최대한 많은 프로그램 을 볼 수 있 도록 하 는 것 이다)
Input 입력 데 이 터 는 여러 개의 테스트 인 스 턴 스 를 포함 합 니 다.각 테스트 인 스 턴 스 의 첫 줄 은 하나의 정수 n(n<=100)만 있 습 니 다.좋아 하 는 프로그램의 총 수 를 나타 내 고 그 다음 에 n 줄 데이터 입 니 다.줄 마다 두 개의 데이터 Ti 가 포함 되 어 있 습 니 다.s,Ti_e(1<=i<=n)는 각각 i 번 째 프로그램의 시작 과 끝 시간 을 나타 내 고 문 제 를 간소화 하기 위해 시간 마다 하나의 정수 로 표시 한다.n=0 은 입력 이 끝 났 음 을 표시 하고 처리 하지 않 습 니 다.
Output 은 모든 테스트 인 스 턴 스 에 대해 전체 적 으로 볼 수 있 는 텔레비전 프로그램의 개 수 를 출력 하고 모든 테스트 인 스 턴 스 의 출력 은 한 줄 을 차지한다.
Sample Input 12 1 3 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9 0
Sample Output 5
문제 풀이 사고:이 문 제 는 간단 한 욕심 사상 으로 이해 할 수 있 고 현재 의 최 적 화 를 매번 의 선택 으로 풀 수 있다.물론 이 문 제 는 각 프로그램의 종료 시간 을 먼저 오름차 순 으로 정렬 한 다음 에 그 핵심 적 인 절 차 는 다음 과 같다.먼저 종료 시간 이 가장 빠 른 프로그램 을 첫 번 째 프로그램 으로 묵인 한 다음 에 종료 시간 과 그 다음 에 종료 시간 이 두 번 째 빠 른 프로그램의 시작 시간 을 비교 하 는 것 이다.만약 에 이 시작 시간 이 종료 시간 보다 빠 르 면 이 프로그램 이 완전 하지 않다 는 것 을 의미한다.그래서 시작 시간 이 늦 어 질 때 까지 첫 번 째 전체 프로그램 을 뒤로 찾 았 다.그리고 계속 밀어.구체 적 인 코드 는 다음 과 같다.
#include
#include
#include
using namespace std;
const int N=105;
typedef struct data
{
int s;
int e;
}data;
int cmp(data x,data y)
{
return x.e// !
}
int main()
{
int n;
data a[N];
while(cin>>n&&n)
{
int k=0,sum=1;
memset(a,0,sizeof(a));
for(int i=0;icin>>a[i].s>>a[i].e;
}
sort(a,a+n,cmp);
for(int i=0;i// , , , , 。
{
if(a[k].e<=a[i].s)
{
sum++;
k=i;
}
}
cout<return 0;
}
개인 적 인 관점 만 을 대표 합 니 다.뿌 려 서 는 안 됩 니 다.교 류 를 환영 합 니 다!!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HPU - ACM 여름 훈련 2 주차 14 급 개인전: Problem D [욕심]Problem D Problem Description 그 러 고 보 니 해동 그룹 이 안팎 으로 어려움 을 겪 고 있 고 회사 의 원로 도 XHD 부부 만 남 았 다 고 한다.분명히 여러 해 동안 싸 운 상인 으로서...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.